首页 > 代码库 > 背包问题
背包问题
01背包:
是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。适合作为动态规划求解。
n个重量为Wi的物品,从中选择若干个使得最终重量v<=w的情况下的价值最大。
输入:
n:样品个数
wi:重量
vi:价值
W:不可超过的重量。
n=4:
(w,v)={(2,3),(1,2),(3,4),(2,2)}
w=5;
输出:7
#include <iostream> using namespace std; const int MAX=100; int dp[MAX][MAX]; int w[MAX],v[MAX]; int n,W; //正序 void slove(){ for(int i=0;i<n;i++){ for(int j=0;j<=W;j++){ if(j<w[i]){ dp[i+1][j] = dp[i][j]; }else{ dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); } } } cout<<dp[n][W]<<endl; } //倒序 void slove1(){ int i,j; for(i=n-1;i>=0;i--){ for(j=0;j<=W;j++){ if(j<w[i]){ dp[i][j] = dp[i+1][j]; }else{ dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); } } } cout<<dp[0][W]<<endl; } int main() { cin>>n>>W; for(int k=0;k<n;k++) cin>>w[k]>>v[k]; //slove(); slove1(); return 0; }
完全背包:
对应n见物品,对应索取出的个数不加以限定
n=3;
(w,v) = {(3,4),(4,5),(2,3)}
w=7;
输出:10;
一个简单算法,不需要考虑每件物品的个数
#include <iostream> using namespace std; /** 完全背包推导: dp[i+1][j] = max(dp[i][j-k*w[i]]+k*v[i],k>=0) dp[i+1][j] = max(dp[i][j],dp[i][j-k*w[i]]+k*v[i],k>=1) dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]-k*w[i]]+k*v[i]+v[i],k>=0) dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); */ const int MAX = 100; int n,W; int dp[MAX][MAX]; int w[MAX],v[MAX]; void slove(){ int i,j; for(i=0;i<n;i++){ for(j=0;j<=W;j++){ if(j<w[i]) dp[i+1][j] = dp[i][j]; else dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); } } cout<<dp[n][W]<<endl; } int main() { cin>>n>>W; for(int k=0;k<n;k++) cin>>w[k]>>v[k]; slove(); return 0; }
上面的情况还可以使用一维数组来实现:
int dp[MAX]; /* 01背包 void slove1(){ int i,j; for(i=0;i<n;i++){ for(j=W;j>=w[i];j--){ dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[W]<<endl; } */ void slove1(){ //完全背包 不需要考虑dp[i+1]状态 只是从重量的角度出发 int i,j; for(i=0;i<n;i++){ for(j=w[i];j<=W;j++){ dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[W]<<endl; }
背包问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。