//先遍历物品
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}int[] weight = {1, 3, 4};
int[] value = {3, 4, 6};
int bagWight = 4;
倒序遍历背包防止重复取物品,因为dp[j-weight[i]]一开始是0
物品0放入所有可以放的背包
i=0,j=4,weight[0]=1,dp[4]=0:dp[4]=max(dp[4],dp[4-0]+value(0))=3
i=0,j=3,weight[0]=1,dp[4]=3,dp[3]=0:dp[4]=max(dp[4],dp[3-0]+value(0))=3
i=0,j=2,weight[0]=1:dp[2]=max(dp[4],dp[2-0]+value(0))=3
i=0,j=1,weight[0]=1:dp[1]=max(dp[4],dp[1-0]+value(0))=3
物品0或1放入所有可以放的背包
i=1,j=4,weight[1]=3,dp[4]=3:dp[4]=max(dp[4],dp[4-3]+value(1))=3+4=7,表示物品0,1都可以放入背包
i=1,j=3,weight[1]=3,dp[4]=7:dp[3]=max(dp[3],dp[3-3]+value(1))=max(3,0+4)=4,表示物品1更大可以放入背包
物品0或1或2放入所有可以放的背包
i=2,j=4,weight[2]=4,dp[4]=7:dp[4]=max(dp[4],dp[4-4]+value(2))=max(7,0+6)=7,表示物品2虽然可以放入背包,但是没有之前的结果大
最终dp[j]结果是:0 3 3 4 7
//先遍历背包容量
for (int j =bagWeight; j >=0; j--){
for (int i = 0; i < wLen&&j >= weight[i]; i++){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}背包容量为4时
j=4,i=0,weight[0]=1,dp[4]=max(dp[4],dp[4-0]+value[0])=3,放入物品0
j=4,i=1,weight[1]=3,dp[4]=3,dp[4]=max(dp[4],dp[4-1]+value[1])=max(3,0+4)=4,对比后放入物品1
j=4,i=2,weight[2]=4,dp[4]=4,dp[4]=max(dp[4],dp[4-2]+value[2])=max(4,0+6)=6,对比后放入物品2
发现无法同时放入物品0和1,背包存的最大值是6,原因是dp[1]里存的还不是物品0的weight,里面是0,若先遍历物品再遍历背包,dp[1]会先存入物品0的weight:3,在后续的dp[4]里会用到这个值
背包容量为3时
j=3,i=0,weight[0]=1,dp[3]=0,dp[3]=max(dp[3],dp[3-0]+value[0])=max(0,3)=3,放入物品0
j=3,i=1,weight[1]=3,dp[3]=3,dp[3]=max(dp[3],dp[3-1]+value[1])=max(3,0+4)=3,对比放入物品1
i=2时,weight[2]=4放不进去
...
最终dp[j]结果是:0 3 3 4 6