01背包问题---（一维数组）

思路

1.定义dp数组

dp[j]:表示为背包容量为j时的最大价值。

2.递推公式

当weight[i]的重量比当前背包的容量小时，说明当前背包可以将物品i放入进来，此时dp[j]=dp[j-物品i的重量]+物品i的价值。此时也可以选择不放进来，则dp[j] = dp[j]。最后dp[j]为二者中最大的。

3.dp数组初始化

dp[0]就是背包容量为0时的价值。应该为0；

4.遍历顺序

因为dp[j]与dp[j-weight[i]]有关，所以就是正序遍历

5.打印顺序

最后的结果就是在数组的最后一个元素。

代码

public void Test01bag(){ int[] weight = {1, 3, 4}; int[] value = {15, 20, 30}; int bagsize = 4; int dp[] = new int[bagsize+1]; dp[0] = 0; for (int i = 0;i=0;j=j-weight[i]){  if(j>=weight[i]){      dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);  }else {      dp[j] = dp[j];  }     } } //打印dp数组 for (int j = 0; j <= bagsize; j++){     System.out.print(dp[j] + " "); }    }