首页 > 代码库 > 01背包问题
01背包问题
01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值,Wi表示第i件物品的重量。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
#include<iostream>#include<vector>using namespace std;vector<int>v;int w[5]={3,3,3,3,3};int p[5]={5,5,5,5,5};void result(int**c,int i,int j);int main(){ int **c=new int*[6]; for(int i=0;i<6;i++) { *(c+i)=new int[11]; } for(int i=0;i<6;i++) { for(int j=0;j<11;j++) { if(i == 0 || j == 0) { c[i][j]=0; } else { if(w[i-1]>j) { c[i][j]=c[i-1][j]; } else { c[i][j]=max(c[i-1][j-w[i-1]]+p[i-1],c[i-1][j]); } } } } cout<<c[5][10]<<endl; result(c,5,10); for(int i=0;i<6;i++) { delete[]*(c+i); *(c+i)=NULL; } delete[]c; c=NULL; return 0;}void result(int**c,int i,int j){ if(i==0 || j==0) { for(int i=0;i<v.size();i++) { cout<<v[i]<<" "; } cout<<endl; return; } if(w[i-1]>j) { result(c,i-1,j); } else { if(c[i-1][j-w[i-1]]+p[i-1] > c[i-1][j]) { v.push_back(i); result(c,i-1,j-w[i-1]); } else if(c[i-1][j-w[i-1]]+p[i-1] == c[i-1][j]) { vector<int>temp(v); v.push_back(i); result(c,i-1,j-w[i-1]); v.swap(temp); result(c,i-1,j); } else { result(c,i-1,j); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。