有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；x是0或1.
3、寻找递推关系式，面对当前商品有两种可能性：
- dp(i,j)表示当前背包容量 j，前 i 个物品最佳组合对应的价值。
- 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即:
- dp(i,j)=dp(i-1,j)；
- 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即
- dp(i,j)=max{ dp(i-1,j)，dp(i-1,j-w(i))+v(i) }。
- 由上述可得：
- j<w(i) dp(i,j)=dp(i-1,j)
- j>=w(i) dp(i,j)=max{ dp(i-1,j)，dp(i-1,j-w(i))+v(i) }
- 填表(垂直 i 轴，横着 j 轴)：
- 表格填完，最优解即是dp(number,capacity)=dp(4,8)=10。
#include<iostream>
using namespace std;
#include <algorithm>
int main() {
int w[5] = {0,2,3,4,5}; //商品的体积2、3、4、5
int v[5] = {0,3,4,5,6}; //商品的价值3、4、5、6
int bagV = 8; //背包大小
int dp[5][9]={{0}};//动态规划表
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= bagV; 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]);
}
}
//动态规划表的输出
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 9; j++) {
cout << dp[i][j] << ' ';
}
cout << endl;
}
//表的最后一行最后一个元素就是结果
return 0;
}
