Posts

好早以前写的，搬运一下 01一维背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}; int n,m; cin>>m>>n; int v,w; while(n--){ cin>>v>>w; for(int i = m ; i >= v; i--) dp[i]=max(dp[i],dp[i-v]+w); } cout<<dp[m]; } 01背包二维 有 n(1 ≤ n ≤ 100) 种物品要放到一个袋子里，袋子的总容量为 m(1 ≤ m ≤ 100) ，我们一共有 k(1 ≤ k ≤ 100) 点体力值。第 i 种物品的体积为 vi(1 ≤ vi ≤ 100) ，把它放进袋子里会获得 wi(1 ≤ wi ≤ 100) 的收益，并且消耗我们 ti(1 ≤ ti ≤ 100) 点体力值，每种物品只能取一次，问如何选择物品，使得在物品的总体积不超过 m 并且花费总体力不超过 k 的情况下，获得最大的收益？请求出最大收益。 #include<bits/stdc++.h> using namespace std; int main() { int n, k, m; cin>>k>>m>>n; int dp[440][440]{}; int v, t, w; while(n--){ cin>>v>>t>>w; for(int i = k; i >= v; i--){ for(int j = m; j >= t; j--){ dp[i][j] = max(dp[i][j],dp[i-v][j-t]+w); } } } cout<<dp[k][m]; return 0; } 完全背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品能用无限多次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}; int m, n; cin>>m>>n; int v,w; while(n--){ cin>>v>>w; for(int i = v; i <= m; i++){ dp[i]=max(dp[i],dp[i-v]+w); } } cout<<dp[m]; } 多重背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 #include<bits/stdc++.h> using namespace std; int main() { int n, m; int dp[100010]{}; cin>>n>>m; int w, v, l; for(int i = 0 ; i < n ; i ++){ cin>>w>>v>>l; while(l--){ for(int j = m; j >= v; j--){ dp[j] = max(dp[j], dp[j-v] + w); } } } cout<<dp[m]; } 多重背包的单调队列优化 多重背包的题: 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 多重背包的二进制优化 ： 题目同上，数据规模为 1 ≤ n, m, l ≤ 2000。用一个定理优化一下。定理：令 t 为最大的 i满足 2i+1 − 1 ≤ n，我们从 1, 2, 4, . . . , 2t, n − 2t+1 + 1 中选一些数字相加（可以不选），可以得出任意 [0, n] 内的值，每个数字只能用一次。每一种物品就只有 log l 个打包，然后对于每一组打包去跑 01 背包，可以把时间复杂度从 O(nm∑l) 降到 O(nm log∑l)。 但显然二进制优化不如单调队列优化，所以我们为什么不直接上单调队列优化呢？ 二进制优化的数据范围：题目同上，数据规模为 1 ≤ n, m, l ≤ 10000。 //二进制优化，抄的谷粒多的板子 #include<bits/stdc++.h> using namespace std; int n, m, v, w, l; int dp[2005]; int main() { cin >> n >> m; while (n--) { cin >> v >> w >> l; for (int k = 1; k <= l; l -= k, k <<= 1) for (int i = m; i >= v * k; i--) dp[i] = max(dp[i], dp[i - v * k] + w * k); for (int i = m; i >= v * l; i--) dp[i] = max(dp[i], dp[i - v * l] + w * l); } cout << dp[m]; return 0; } //单调队列优化 //没看懂，还是抄的谷粒多板子。。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> using namespace std; int n, m, V[210], W[210], C[210]; int f[20010], q[20010]; int calc(int i, int u, int k) { return f[u + k * V[i]] − k * W[i]; } int main() { cin >> n >> m; memset(f, 0xcf, sizeof(f)); // −INF f[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &V[i], &W[i], &C[i]); for (int u = 0; u < V[i]; u++) { int l = 1, r = 0; int maxp = (m - u) / V[i]; for (int k = maxp - 1; k >= max(maxp - C[i], 0); k--) { while (l <= r && calc(i, u, q[r]) <= calc(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) f[u + p * V[i]] = max(f[u + p * V[i]], calc(i, u, q[l]) + p * W[i]); if (p - C[i] - 1 >= 0) { while (l <= r && calc(i, u, q[r]) <= calc(i, u, p - C[i] - 1)) r--; q[++r] = p - C[i] - 1; } } } } int ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, f[i]); cout << ans << endl; } 分组背包 有 n 种物品要放到一个袋子里，袋子的总容量为 m。第 i 个物品属于第 ai 组，每组物品我们只能从中选择一个。第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 #include<bits/stdc++.h> using namespace std; int main() { int n, m, v, w, dp[1010]{}, a; cin>>n>>m; vector<pair<int,int>>c[1010]; for(int i = 1; i<= n; i++) { cin>>a>>v>>w; c[a].push_back({v,w}); } for(int i =0 ; i<=1000;i++){ for(int j = m; j>=0; j--){ for(auto [l,r]:c[i]){ if(v<=j) dp[j]=max(dp[j],dp[j-l]+r); } } } cout<<dp[m]; return 0; } 混合背包 混合背包比较愚蠢，很显然，如果是01，那么就直接取01；如果是完全，那就完全，如果是多重那就多重。 #include<bits/stdc++.h> using namespace std; int main() { int dp[100010]{}, n, m; cin>>n>>m; int t, v, w; while(n--){ cin>>t>>v>>w; if(t==1){ for(int i = m; i >= v; i--) dp[i] = max(dp[i], dp[i-v] + w); } else if(t==0){ for(int i = v; i <= m; i++) dp[i] = max(dp[i], dp[i-v] + w); } else { while(t--){ for(int i = m; i>= v; i--) dp[i] = max(dp[i], dp[i-v] + w); } } } cout<<dp[m]; return 0; } 有依赖的背包 题目：金明有 n 元钱，想要买 m 个物品，第 i 件物品的价格为: ，重要度为: 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。 目标是让所有购买的物品的: 之和最大。 这种题目比较愚蠢，就懒得写代码了，把主件当01背包做，把附件的代码+主件的代价，再把附件当做分组背包做即可。 k优解 不会 前后缀分解 显然对于01背包而言，存在需要放进去的物品和不需要放进去的物品，现在清楚姐姐有个问题，题目如下： ...