背包问题：
有一个背包可以承受固定的重量，承受重量自己输入
现在有很多物品，每个物品有自己的价值和价格，物品的个数，质量和价值可以自己输入
求：在背包的承受重量范围内，放置哪些物品到背包才能使得背包中物品的总价值最大。
二维动态规划：
我们这样想象，物品是一个一个到来的，当这个物品来时，我们仅有两种选择，装入背包或者不装入背包。
假设，现在有 i 个物品，这 i 个物品选择放入背包（承重为10kg）中已经达到了价值最大值（也就是结果）。
那么 第 i 个物品肯定要么装入背包，要么不装入背包。
假设不装入背包，那么 1 到 i 个物品装入 10kg 背包就能被简化为 1 到 i -1 个物品装入 10kg 背包问题。
假设装入背包，那么问题就会被简化为 1 到 i-1 个物品装入 （10kg - 第 i 个背包的重量）的背包问题。
上述就时动态规划的递推关系。
由于我们如果想要知道 i 个物品放入 10kg ，我们需要知道 i-1 个物品放入 10kg 或者 i-1 个物品放入 10kg - 第i个背包的重量。物品和重量在递推中都起到了作用，所以说二维动态规划更容易。
设dp[ i ] [ j ] 是 1 - i 个 物品 放入 j kg 的背包容量中的最大价值
if(放入第i个){
dp [ i ] [ j ] = dp [ i-1 ][ j-第i个物品的重量 ] + 第 i 个物品的价值
}
if(不放第i个){
dp[ i ] [ j ] = dp[ i-1 ][ j ];
}
初始条件是：如果物品个数为 0 或者 背包容量为 0 那么就dp 就为 0 ;
import com.sun.javafx.collections.MappingChange;
import java.util.*;
public class Test {
public static void main(String[] args) {
//背包问题是典型的动态规划问题 给定一个背包的容量（只能装一定质量的物品） 先有很多的物品 他们具有不同的价格和质量 求怎样装这个背包中的物品价格之和最大
int bagWeight = 10; //书包承受的重量
int objs_num = 10;
int[][] objs = new int[objs_num][2];//物品的总个数
init(objs);
int[][] dp = new int[objs.length+1][bagWeight+1];
for(int i=0;ij){
dp[i][j] = dp[i-1][j]; //既然没有装的话 那就是等于最后一个物品没来之前的总价值
}else {
//现在是能装下了，到底装还是不装呢？
//如果装入了，那么就等于之前i-1个物品转入之前的容量 ，装入之前要预留好空间，所以之前的空间是j-objs[i-1][0]，之前的物品个数是i-1
int in = dp[i-1][j-objs[i-1][0]]+objs[i-1][1];
//不装入的话就等于之前i-1个物品来的时候
int noIn = dp[i-1][j];
dp[i][j] = Math.max(in,noIn); //取两个中最大的
}
}
}
}
int res = dp[objs.length][bagWeight];
ArrayList objs1 = findObjs(dp,objs,objs.length,bagWeight,new ArrayList<>());
System.out.println("装入的物品是:");
for(int i=0;i findObjs(int[][] dp,int[][] objs,int i,int j,ArrayList res){
//i 代表的是当前判断的某物品在不在，j代表的是预留的空间
if(j==0||i==0){
//没空间了就返回
return res;
}
if(dp[i][j]==dp[i-1][j]){
//说明没方第i个物品
findObjs(dp,objs,i-1,j,res);
}else{
//说明放了第i个物品，为 i 预留空间
res.add(i-1);
findObjs(dp,objs,i-1,j-objs[i-1][0],res);
}
return res;
}
} 
