题目链接

/problem/content/2/

思路

对于每一个物品我们能做一个选择，选上它(前提是当前的剩余背包容量够)，或者不选，那么我们只需要在这其中取一个max即可，我们定义一个f[i][j]f[i][j]f[i][j]表示的含义是从前i个物品中选择背包容量最多为j的价值，那么我们只需要考虑当前第i个物品的取舍，也就是f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])，由于我们这个转移方程只会用到上一层的状态以及当前这一层的状态，所以我们再通过滚动数组优化为f[j]=max(f[j],f[j−v[i]]+w[i])f[j] = max(f[j],f[j-v[i]] + w[i])f[j]=max(f[j],f[j−v[i]]+w[i])

代码

#include<bits/stdc++.h>using namespace std;const int N = 1000+10;int f[N],n,v,V[N],W[N];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){f[j] = max(f[j],f[j-V[i]] + W[i]);}}printf("%d\n",f[v]);return 0;}