有 N 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 NN 行，每行两个整数 vi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
1.二维循环
dp[i][j]表示在考虑前i种物品，在体积为j时候的最大价值
dp[i][j]={dp[i-1][j-v[i]]+w[i],dp[i-1][j]}
#include<bits/stdc++.h> using namespace std; int value[1005]; int weight[1005]; int dp[1005][1005]; int main() { int N,V; cin>>N>>V; for(int i=1;i<=N;i++) { cin>>weight[i]>>value[i]; } memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++) { for(int j=1;j<=V;j++) { if(i==1) dp[i][j]=j>=weight[1]?value[i]:0; else { if(j>=weight[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); else dp[i][j]=dp[i-1][j]; } } } cout<<dp[N][V]<<endl; }
2.一维循环
由上面二维循环可以知道，dp[i][j]的值依赖于dp[i-1][j]
如果我们去掉一维dp[i]，如果采用顺序方式，改变了原有转移方程，只有采用逆序才能保证每个都是依赖上一层的
因为这样才不会受这次影响#include<bits/stdc++.h> using namespace std; int value[1005]; int weight[1005]; int dp[1005]; int main() { int N,V; cin>>N>>V; for(int i=1;i<=N;i++) { cin>>weight[i]>>value[i]; } memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++) { for(int j=V;j>=weight[i];j--)//采用倒叙 { dp[j]=max(dp[j-weight[i]]+value[i],dp[j]); } } cout<<dp[V]<<endl; }
原文链接: https://www.cnblogs.com/Charls/p/12771772.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/344432
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
