组合数、01背包、完全背包

诗 槐作者： • 2025-03-14 • 算法

组合数:

求范围组合数:(有点dp的感觉)

https://www.starrycoding.com/problem/45

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e3 + 9;
const int M = 1e9 + 7;
int a[N][N];
void solve() {
  int n, m;
  cin >> n >> m;
  a[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      a[i][j] = (a[i - 1][j - 1] % M + a[i - 1][j] % M) % M;
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

求单独:用乘法逆元

https://www.starrycoding.com/problem/46

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e9 + 7;
const int B = 1e7 + 9;
int fac[B];
int fastabs(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = res * a % N;
    a = a * a % N;
    b >>= 1;
  }
  return res;
}

void factorial() {
  fac[0] = 1;
  for (int i = 1; i < 1e7; i++) fac[i] = fac[i - 1] * i % N;
}
int MOX(int n, int m) {
  return ((fac[n] % N) % N * fastabs(fac[n - m] * fac[m] % N, N - 2) % N) % N;
}

void solve() {
  int n, m;
  cin >> n >> m;
  cout << MOX(n, m) << endl;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  factorial();
  int _;
  cin >> _;
  while (_--) solve();
  return 0;
}

https://www.starrycoding.com/problem/73

没看明白

01背包:

朴素:

外层循环从小到大,内层循环从小到大,外层循环从1开始,内层循环从0开始

滚动优化:(只有两行的数组)

转化模板:

//转化为二维:int dp[2][M];
//声明一个y int y = i & 1;//写哪里都不影响
//将i替换为y,i-1替换为y^1,n替换为n&1,只换二维dp的行
//多次询问需要清空:for (int i = 0; i <= T; i++) dp[0][i] = 0;

一维优化:

优化模板:

//转化为一维:int dp[N];
//将所有的dp行维删除,将内循环的遍历倒置,初始维最大,结束为最小,对于0/1背包,需要倒置,对于完全背包,无需倒置
//多次询问需要清空:for (int i = 0; i <= T; i++) dp[i] = 0;

https://www.starrycoding.com/problem/74

朴素:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int T, M;
int t[105], v[105];
int dp[105][1009];
void solve() {
  for (int i = 1; i <= M; i++) {
    cin >> t[i] >> v[i];
  }
  for (int i = 1; i <= M; i++) {
    for (int j = 0; j <= T; j++) {
      if (j >= t[i])
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + v[i]);
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
  cout << dp[M][T] << endl;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> T >> M) {
    if (T == 0 && M == 0) break;
    solve();
  }
  return 0;
}

滚动优化:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int T, M;
int t[105], v[105];
int dp[2][1009];
void solve() {
  for (int i = 0; i <= T; i++) dp[0][i] = 0;//清空,多次询问
  for (int i = 1; i <= M; i++) cin >> t[i] >> v[i];
  for (int i = 1; i <= M; i++) {
    int y = i & 1;
    for (int j = 0; j <= T; j++) {
      if (j >= t[i])
        dp[y][j] = max(dp[y ^ 1][j], dp[y ^ 1][j - t[i]] + v[i]);
      else
        dp[y][j] = dp[y ^ 1][j];
    }
  }
  cout << dp[M & 1][T] << endl;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> T >> M) {
    if (T == 0 && M == 0) break;
    solve();
  }
  return 0;
}

一维优化:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int T, M;
int t[105], v[105];
int dp[1009];
void solve() {
  for (int i = 0; i <= T; i++) dp[i] = 0;
  for (int i = 1; i <= M; i++) cin >> t[i] >> v[i];
  for (int i = 1; i <= M; i++) {
    for (int j = T; j >= 0; j--) {
      if (j >= t[i])
        dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
      else
        dp[j] = dp[j];
    }
  }
  cout << dp[T] << endl;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> T >> M) {
    if (T == 0 && M == 0) break;
    solve();
  }
  return 0;
}

完全背包:

https://www.starrycoding.com/problem/47

朴素:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e2 + 5;
const int M = 1e5 + 5;
int w[N], v[N];
int dp[N][M];
void solve() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (j >= v[i])
        dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
  cout << dp[n][m];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

滚动优化:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e2 + 5;
const int M = 1e5 + 5;
int w[N], v[N];
int dp[2][M];
void solve() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; i++) {
      int y = i & 1;
    for (int j = 0; j <= m; j++) {
      if (j >= v[i])
        dp[y][j] = max(dp[y ^ 1][j], dp[y][j - v[i]] + w[i]);
      else
        dp[y][j] = dp[y ^ 1][j];
    }
  }
  cout << dp[n & 1][m];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

一维优化:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e2 + 5;
const int M = 1e5 + 5;
int w[N], v[N];
int dp[M];
void solve() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (j >= v[i])
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
      else
        dp[j] = dp[j];
    }
  }
  cout << dp[m];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

多重背包:

转化为01背包,利用01背包的思路,多一层每个物品的数量的循环,利用while循环将重复物品拆分即可

while (s--) {
      for (int j = m; j >= 0; j--) {
        if (j >= v)
          dp[j] = max(dp[j], dp[j - v] + w);
        else
          dp[j] = dp[j];
      }
    }

https://www.starrycoding.com/problem/75

一维优化:

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e2 + 5;
const int M = 1e4 + 9;
int dp[M];
void solve() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    int s, w, v;
    cin >> s >> w >> v;
    while (s--) {
      for (int j = m; j >= 0; j--) {
        if (j >= v)
          dp[j] = max(dp[j], dp[j - v] + w);
        else
          dp[j] = dp[j];
      }
    }
  }
  cout << dp[m];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

若你所见,这里我还不知道加什么
要不要加个彩蛋呢

滚动至顶部