1 条题解
-
1XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2024-09-29 16:07:14
普通背包:P1002 灰灰的婚姻
当\(w\)权值过大导致无法开对应大小的数组时,如果\(v\)范围较小,可以考虑用\(v\)价值来开数组。
设\(dp[i][j]\)表示 “只考虑前\(i\)个物品的 情况下,总价值是\(j\)所需的最小容量”。那么在计算\(dp[i][j]\)的时候,所有情况 依然可以分成两类考虑:
拿第\(i\)件物品,那么别的物品的总价值需要凑出\(j−v_i\),而由于每样物品只能拿一件,所以我们只需要考虑前\(i−1\)件物品的最优选取方式,即最终重量为\(dp[i−1][j−v_i]+wi\)。
不拿第\(i\)件物品,那么别的物品需要凑出\(j\)的价值。由于我们选择不拿第\(i\)件物品,现在只需要考虑前\(i−1\)件物品的最优选取方式,即最小重量为\(dp[i−1][j]\)。
计算完所有状态的值后,只需要选取满足重量上限的最大价值即可。
然后呢,我们还可以参照01背包的方法,将状态转移方程压成1维。
故,我们可得本题的状态转移方程为:\(dp[j]=min(dp[j],dp[j−v[i]]+w[i])\)
代码如下
#include <bits/stdc++.h> #define MAXN 100005 #define INF 1e9 #define FILE_IO false #define DISCONNECT_WITH_STDIO true using namespace std; int f[100005], w[101], v[101], N, W, maxValue; int main() { cin>>N>>W; for(int i=1; i<=N; i++){ cin>>w[i]>>v[i]; } memset(f, 0x3f, sizeof f); f[0] = 0; maxValue = N*1000; for(int i=1; i<=N; i++){ for(int j=maxValue; j>=v[i]; j--){ f[j] = min(f[j], f[j-v[i]]+w[i]); } } for(int i=maxValue; i; i--){ if (f[i] <= W){ cout<<i; return 0; } } return 0; }
- 1
信息
- ID
- 1070
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者