问题 当前有一个容量为5的背包 有三种商品价值和质量分别为 ：
1 v = 6；w=1；
2 v=10；w=2；
3 v=12 ；w=3；
求解不超过背包容量的情况下获取最大值的商品。
此类问题应该用动态规划的方式进行求解，将背包的容量进行一个分解；分解为1-5；然后将1-3号商品逐一添加到容量不同的背包中去。图解如下
1.png
该算法的核心思想就是当容量足够可以放入一个物品的时候你要将这个值与你之前的最优解进行一个比较
就是 当前物品的价值+背包减去此物品w后的最优解 与 不放这个物品时的最优解进行比较。
代码如下
public static void main(String[] args) {
int r = 5;
int[] v= {6,10,12};//物品的质量
int[] w = {1,2,3};//物品的重量
//构造这个二维数组，其实这个二维数组就是之前图中所画的那个数组
int[][]dp = new int[4][6];
int n = v.length;//物品的数量
for(int i= 0;i<dp.length;i++ ){//给dp一个初始值
for(int j = 0;j<dp[0].length;j++){
dp[i][j]=0;
}
}
//循环物品的数量
for(int i = 1;i<=n;i++){
//循环背包的容量
for(int j = 1;j<=r;j++){
if(w[i-1]<=j){
dp[i][j]=Math.max((v[i-1]+dp[i-1][j-w[i-1]]), dp[i-1][j]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
for(int i= 0;i<dp.length;i++ ){//打印出dp的结果
for(int j = 0;j<dp[0].length;j++){
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
}
