3.8 0-1背包问题(Knapsack problem)
前言：麻烦转载注明出处哦。
3.8.1 问题描述
其中每种物品只有1件，存放哪些物品，才能使背包存放物品价值最高？
3.8.2 算法思路
假设背包空间只有1kg、2kg…5kg，假设可装物品只有1种、2种…4种，按照这种思想，我们可以得出下面这张表。
要填写这张表，首先要知道每个空格之间的依赖关系。
以下图的最后一张表为例：当剩余空间为3kg，剩余商品为1号(2kg,12元)、2号 (1kg,10元)，此时，我们有两种选择：
- 第一种，选择不放入2号商品，这意味着剩余空间为3kg，剩余商品为1号(2kg,12元)，则可以直接填入橙色那格的数值，即12；
- 第二种，选择放入2号商品，这意味着剩余空间为1，剩余商品为1号(2kg,12元)，这种情形对应着图中绿色的内容格，并且再将其加上2号商品的价格10元，10+12=22。
综上，比较两种方案的值，填入大的，即填入22。
按照这样的填法，我们填完了整张表，即下图。左下角的值37，即背包装入的最大价值。
现在要研究，怎么从这张表看出，应该放入哪些商品。
从最下角开始看：
- 37不等于32，等于22+15，说明4号商品放入了，此时，剩余空间为3kg，剩余物品为1号(2kg,12元)、2号 (1kg,10元)、3号(3kg,20元)，也就是第三行蓝色位置
- 22等于22，说明3号商品不放入，此时，剩余空间为3kg，剩余物品为1号(2kg,12元)、2号 (1kg,10元)，也就是第二行蓝色位置
- 22不等于12，等于12+10，说明2号商品放入了，此时，剩余空间为2kg，剩余物品为1号(2kg,12元)，也就是第二行蓝色位置。
- 12不等于0，等于0+12，说明1号商品放入了，此时，剩余空间为0kg，剩余物品为0，也就是第一行蓝色位置。
综上，放入1、2、4号商品。
注意：上述的演示图没有写剩余空间为0或者剩余商品为0的情况，在代码实现时，为了让首行的处理与其他行相同，需要从0开始考虑。
3.8.3 代码实现
public static LinkedList<Integer> getByTabulation(int[][] items,int capacity){//item:商品,capacity:空间
int n=item.length;
int[][] tab=new int[n+1][capacity+1];//多一行一列，放物品0或空间0的可能。java数组初始值为0
/*核心*/
for(int i=1;i<n+1;i++){
for(int c=1;c<capacity+1;c++){
if(c-items[i-1][0]>0){//剩余空间大于当前商品重量
tab[i][c]=Math.max(tab[i-1][c],items[i-1][1]+tab[i-1][c-items[i-1][0]]);//放或者不放，两种方案中的最大值
}else{
tab[i][c]=tab[i-1][c];//放不下，只能选择不放
}
}
}
LinkedList<Integer> packedItem=new LinkedList<Integer>();
int c=capacity;
/*核心*/
for(int i=n;i>0;i--){//找出装入了哪些物品
if(tab[i][c]!=tab[i-1][c]){//不等于上一行的值，说明放入了当前商品
packedItem.add(0,i);//每次都插入链表的第一个位置，前面插入的自动后移。保存放入物品的序号。
c=c-item[i-1][0];
}
}
return packedItem;
}