首页 > 代码库 > 动态规划三：0-1背包问题
动态规划三：0-1背包问题
1.问题描述：
一定的物体和一背包，物体i的重量为wi价值为vi，背包的容量为c，求解怎样放使背包的价值最大？则问题可描述为：
2.问题分析：
1）最优子结构：
其中j=c-wiyi
2）递归关系：设最优值为m(i,j)，j表示最优容量，i表示可选物品，由最优子结构性质可建立递归式：
3.算法描述：(未优化)
1 #include<iostream> 2 using namespace std; 3 int c[10][100]; 4 int Knap(int m, int n){ 5 int w[10]; 6 int v[10]; 7 cout << "输入物体重量w和价值v：\n"; 8 for (int i = 1; i <= n; i++){ 9 cin >> w[i] >> v[i];10 }11 for (int i = 1; i <= n; i++)12 {13 for (int j = 1; j <= m; j++)//背包的容量则逐一测试14 {15 if (w[i] <= j)16 {17 if (c[i - 1][j] < v[i] + c[i - 1][j - w[i]])18 c[i][j] = v[i] + c[i - 1][j - w[i]];19 else20 c[i][j] = c[i - 1][j];21 }22 else23 c[i][j] = c[i - 1][j];24 }25 }26 return c[n][m];27 }28 29 int main(){30 int n, m;31 cout << "输入物体数n和背包容量m:\n";32 cin >> n >> m;33 cout << Knap(n, m)<<endl;34 for (int i = 0; i <= n; i++)35 {36 for (int j = 0; j <= m; j++)37 cout<<c[i][j];38 cout<<endl;39 }40 return 0;41 }
动态规划三：0-1背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。