问题

对于一组不同重量、不可分割的物品，选择一些物品放入到背包中，在满足背包可以承受的最大重量下，能放入背包的物品最大重量值是多少？

解题思路

是否属于动态规划

判断该问题是否是动态规划问题，需要判断是否存在最优子结构、重合子问题

假设，有3个物品，重量分别是2、3、5，背包的最大承重为11。

当我们将3个物品全放入背包中时，剩下的背包承重的最优解，其实就是整个问题的最优解。所以该问题存在最有子结构。

是否存在重复子问题，我们可以通过画递归树来区分

通过上图的递归树可以看到，在寻找子问题时，时存在重复子问题的。

所以，背包问题是可以用动态规划来解决问题。

套路

初始化base case
dp[0][0][……] = base;
##状态转移
for 状态1 in 状态1的所有值
for 状态2 in 状态2的所有值
for 状态n…..
dp[状态1][状态2][…..] = 求最值（选择1、选择2、…..）

伪代码

假设，有3个物品，重量分别是2、3、5，背包的最大承重为11。

定义放入N个物品后，背包是否可以承受总重量。
比如：选择第1个物品后，有两种状态，A：选择放入背包，背包重量为2，B：不放入背包，背包重量为0
所以对应的状态值为 dp[0][0]，dp[1][2]，dp数组的一维元素代表放入的物品个数，二维元素代表一维元素选择后背包的重量

初始化base case，初始化值都设置为0，表示没有物品放入背包
w=11 ##背包可承受的总重量
weight = int{2,3,5}; ##物品重量
n = 3 ##物品个数
boolean[][] dp = new boolean[n][w+1]; ##状态初始化
Arrays.fill(dp,false);
dp[0][0]=true;
for( int i =1 : n){
if(weight[i] < =w){
dp[0][weight[i]] = true;
}
}

for( int i =1 : n){

如果不把第i个物品放入背包，则背包承重不变
for(int j : w){
if(dp[i-1][j] == true) dp[i][j] = true;
}
##如果把第i个物品放入背包，则背包承受的重量为w-weight[i]
for(int j : w-weigth[i]){
if(dp[i-1][j]==true) dp[i][j+weigth[i]] =true;
}

}
for(int i =w ; i>=0 ;i—){
if(dp[n-1][i] == true ) return i;
}