Acwing2 01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出一个整数,表示最大价值。
0<N,V≤10000
0<vi,wi≤10000
4 5
1 2
2 4
3 4
4 5
8
#include<bits/stdc++.h> using namespace std; const int M = 1e3 + 7; int v[M], w[M], dp[M], N, V; int main() { scanf("%d%d", &N, &V); for (int i = 1; i <= N; i++) { scanf("%d%d", &v[i], &w[i]); } for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { dp[j] = max(dp[j - v[i]] + w[i], dp[j]); } } printf("%d\n", dp[V]); return 0; }
Acwing3 完全背包问题
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出一个整数,表示最大价值。
0<N,V≤10000
0<vi,wi≤10000
4 5
1 2
2 4
3 4
4 5
10
#include<bits/stdc++.h> using namespace std; const int M = 1e3 + 7; int v[M], w[M], N, V, dp[M]; int main() { scanf("%d%d", &N, &V); for (int i = 1; i <= N; i++) { scanf("%d%d", &v[i], &w[i]); } for (int i = 1; i <= N; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } printf("%d\n", dp[V]); return 0; }
Acwing4 多重背包问题1
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出一个整数,表示最大价值。
0<N,V≤1000
0<vi,wi,si≤1000
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10
#include<bits/stdc++.h> using namespace std; int main() { int n, V; cin >> n >> V; vector<int> v(n + 1); vector<int> w(n + 1); vector<int> s(n + 1); vector<int> dp(V + 1); for (int i = 0; i < n; i++) { cin >> v[i] >> w[i] >> s[i]; } for (int i = 0; i < n; i++) { for (int j = V; j >= v[i]; j--) { for (int k = 1; k <= s[i]; k++) { if (j >= k * v[i]) dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]); } } } printf("%d\n", dp[V]); return 0; }
Acwing5 多重背包问题2
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出一个整数,表示最大价值。
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
本题考查多重背包的二进制优化方法。
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; int vv[maxn], ww[maxn], s[maxn], N, V, v[maxn]; int dp[maxn], w[maxn]; int get(int x) { int p = 0, tot = 0; for (int i = 0; ; i++) { tot += pow(2, i); if (tot <= x) { p = i; } if (tot >= x) break; } return p; } int main() { int cnt = 0; cin >> N >> V; for (int i = 0; i < N; i++) { cin >> vv[i] >> ww[i] >> s[i]; } for (int i = 0; i < N; i++) { int p = get(s[i]); int R = s[i] - pow(2, p + 1) + 1; for (int j = 0; j <= p; j++) { v[++cnt] = pow(2, j) * vv[i], w[cnt] = ww[i] * pow(2, j); } if (R) v[++cnt] = R * vv[i], w[cnt] = ww[i] * R; } for (int i = 1; i <= cnt; i++) { for (int j = V; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } cout << *max_element(dp, dp + 1 + V) << endl; return 0; }
Acwing6 多重背包问题3
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
第一行两个整数,N,V ,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出一个整数,表示最大价值。
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000
本题考查多重背包的单调队列优化方法。
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10
#include<bits/stdc++.h> using namespace std; const int M = 2e4 + 7; int v[M], w[M], s[M], dp[M], q[M], N, V; int cal(int i, int u, int k) { return dp[u + k * v[i]] - k * w[i]; } int main() { scanf("%d%d", &N, &V); for (int i = 1; i <= N; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); for (int u = 0; u < v[i]; u++) { int l = 1, r = 0; int maxp = (V - u) / v[i]; for (int k = maxp - 1; k >= max(maxp - s[i], 0); k--) { while (l <= r && cal(i, u, q[r]) <= cal(i, u, k)) r--; q[++r] = k; } for (int p = maxp; p >= 0; p--) { while (l <= r && q[l] > p - 1) l++; if (l <= r) dp[u + p * v[i]] = max(dp[u + p * v[i]], cal(i, u, q[l]) + p * w[i]); if (p - s[i] - 1 >= 0) { while (l <= r && cal(i, u, q[r]) <= cal(i, u, p - s[i] - 1)) r--; q[++r] = p - s[i] - 1; } } } } int ans = 0; for (int i = 1; i <= V; i++) ans = max(ans, dp[i]); printf("%d\n", ans); return 0; }
Acwing7 混合背包问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 ii 种物品的体积、价值和数量。
输出一个整数,表示最大价值。
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
8
#include<bits/stdc++.h> using namespace std; const int M = 2e4 + 7; int v[M], w[M], s[M], dp[M], q[M], N, V; int cal(int i, int u, int k) { return dp[u + k * v[i]] - k * w[i]; } int main() { scanf("%d%d", &N, &V); for (int i = 1; i <= N; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); if (s[i] > 0) { for (int u = 0; u < v[i]; u++) { int l = 1, r = 0; int maxp = (V - u) / v[i]; for (int k = maxp - 1; k >= max(maxp - s[i], 0); k--) { while (l <= r && cal(i, u, q[r]) <= cal(i, u, k)) r--; q[++r] = k; } for (int p = maxp; p >= 0; p--) { while (l <= r && q[l] > p - 1) l++; if (l <= r) dp[u + p * v[i]] = max(dp[u + p * v[i]], cal(i, u, q[l]) + p * w[i]); if (p - s[i] - 1 >= 0) { while (l <= r && cal(i, u, q[r]) <= cal(i, u, p - s[i] - 1)) r--; q[++r] = p - s[i] - 1; } } } } else if (!s[i]) { for (int j = v[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } else { for (int j = V; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } } int ans = 0; for (int i = 1; i <= V; i++) ans = max(ans, dp[i]); printf("%d\n", ans); return 0; }
Acwing8 二维费用的背包问题
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值。
第一行两个整数,N,V, M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出一个整数,表示最大价值。
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
8
#include<bits/stdc++.h> using namespace std; const int SZ = 1e3 + 7; int dp[SZ][SZ], v[SZ], m[SZ], w[SZ], N, V, M; int main() { scanf("%d%d%d", &N, &V, &M); for (int i = 1; i <= N; i++) { scanf("%d%d%d", &v[i], &m[i], &w[i]); } for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { for (int k = M; k >= m[i]; k--) { dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]); } } } printf("%d\n", dp[V][M]); return 0; }
Acwing9 分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。
接下来有 N 组数据:
输出一个整数,表示最大价值。
0<N,V≤100
0<Si≤100
0<vij,wij≤100
3 5
2
1 2
2 4
1
3 4
1
4 5
8
#include<bits/stdc++.h> using namespace std; const int maxn = 1e2 + 7; int N, V, s[maxn], v[maxn][maxn], w[maxn][maxn], dp[maxn]; int main() { cin >> N >> V; for (int i = 1; i <= N; i++) { cin >> s[i]; for (int j = 1; j <= s[i]; j++) cin >> v[i][j] >> w[i][j]; } for (int i = 1; i <= N; i++) { for (int j = V; j >= 0; j--) { for (int k = 1; k <= s[i]; k++) { if (j >= v[i][k]) dp[j] = max(dp[j - v[i][k]] + w[i][k], dp[j]); } } } cout << *max_element(dp, dp + 1 + V) << endl; return 0; }
原文:https://www.cnblogs.com/HighLights/p/13287226.html