1.什么是01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
对于物品来说只有两个状态，取或者不取，取为1不取为0，因此叫做0-1背包问题，下面我们通过一个实际的例子来进行说明。
2.背包问题例子
题：假设现在有a,b,c,d,e五块💎，分别的重量为2，2，6，5，4，价值分别为 6，3，5，4，6;问：我们目前的背包容量为10，怎么装💎才能使获取的价值最大？
对应的表格示例：
| 💎 | a | b | c | d | e |
|---|---|---|---|---|---|
| 容量 | 2 | 2 | 6 | 5 | 4 |
| 价值 | 6 | 3 | 5 | 4 | 6 |
对于我们人去操作的话，首先考虑的就是质量轻，并且价值大的，从数据中，我们可以看到💎a质量最小，且价值最大，应该优先考虑这一块，然后再去考虑其他的。这种方式就是考虑性价比最高的💎，我们可以将这个问题进行简化，目前背包的容量为10，因此我们的选择较多，不知道如何去下手，那么我们假设背包的容量为5或者是3甚至是2或者1.在这种情况下，我们的选择就不多了，对于人类的选择也是，在选择不多的情况下更容易找出最优方案。同样对于计算机也是。
因此我们的背包问题也是从这里开始，将选择较多的问题转化为选择不多的问题。在选择不多的情况下进行选择，有利于比较判断，依次递增，最后解决背包容量为10的问题。
对于背包问题，其实就是一个动态规划，大多数都是使用一个数组来进行保存，对于初学者而言，都不知道这个数组是如何推断出来的，别着急，耐心看，下面我们就一步一步来解释该数组是怎么来的，公式是如何推导出来的。
3.公式推导解释
-
首先考虑背包的容量为0的时候，当然是一块宝石都不能装，同样假设背包容量为1，也是一块宝石也不能装。
-
接下来考虑容量为2的时候，这时候就需要分情况进行考虑了。
每次装的时候都把背包的容量当成初始值来装。
这里先定义一个数组dp【i】【j】来表示，为了方便记录。 表示当i物品放入容量为j的背包中，此时最大的价值为dp【i】【j】
-
考虑💎a，a的容量为2，目前背包的容量为2，装--价值为6，不装--价值为0--所以选择装，此时价值为6， dp【a】【2】 = 6
-
考虑💎b，b的容量为2，目前背包的容量为2，tip（因为💎是从前->后依次装的，所以在装后一个时候需要考虑到前一个已装的情况）。dp【b】【2】
💎b的容量小于等于背包的容量，所以装： 装的时候需要考虑装了的价值，是装的时候大，还是不装的时候大 不装---价值是前一个💎a装的价值，也就是装💎a背包容量为2的时候，价值==6，此时的 dp【a】【2】==6 装-----因为💎b也是有容量的，所以需要考虑前一个💎a在装的时候背包容量（背包容量2-💎b的容量）的最大价值，此时的 dp【a】【2-2】+3= dp【a】【0】 + 3 = 0 + 3 = 3 取大的那一个，所以使用Math.max(dp[a][2],dp[a][0]+3)=dp[b][2] -
对于💎c，💎d，💎e来说，容量2的背包不足以装下任意一颗💎，所以不考虑，因此在背包容量为2的时候，选择放💎a，价值最大，为6
-
- 现在难度升级，考虑背包的容量为4（容量为3的时候，解决方案和承容量2时的思路是一致，方案相同，不作叙述）(最重要的部分！！！)
-
考虑💎a，目前背包容量为4，装--价值为6，不装---价值为0--所以选择装，价值为6 ，dp【a】【4】 = 6
-
考虑💎b，目前背包容量为4
💎b的容量小于等于背包的容量，所以装： 装的时候需要考虑装了的价值，是装的时候大，还是不装的时候大 不装---价值是前一个💎a装的价值，也就是装💎a背包容量为4的时候，价值==6，此时的 dp【a】【4】==6 装-----因为💎b也是有容量的，所以需要考虑前一个💎a在装的时候背包容量（背包容量4-💎b的容量）的最大价值，此时的 dp【a】【4-2】+3= dp【a】【2】 + 3 = 6 + 3 = 9 取大的那一个，所以使用Math.max(dp[a][4],dp[a][2]+3)=dp[b][4]==9 -
考虑💎c，目前背包容量为4，装--需要6的容量，不考虑 dp【c】【4】 = dp【b】【4】 = 9
-
考虑💎d，目前背包容量为4，装--需要5放入容量，所以不考虑 dp【e】【4】 = dp【c】【4】 = 9
-
考虑💎e，目前背包容量为4，装--需要4放入容量，要考虑装或者不装时候的价值
💎e的容量小于等于背包的容量，所以装： 装的时候需要考虑装了的价值，是装的时候大，还是不装的时候大 不装---价值是前一个💎d装的价值（其实根据上述的推导其实是dp【b】【4】的最大价值） dp【d】【4】==dp【c】【4】=dp【b】【4】=9 --》 dp【d】【4】==9 装-----因为💎e也是有容量的，所以需要考虑前一个💎d在装的时候背包容量（背包容量4-💎e的容量）的最大价值，此时的 dp【d】【4-4】+6= dp【d】【0】 + 6 = 0 + 6 = 6 取大的那一个，所以使用dp[e][4]=Math.max(dp[d][4],dp[d][0]+6)==9
4.代码示例及输出结果
/**
*
* @param weight 物品的重量
* @param values 物品的价值
* @param cap 背包可以承受的重量
* @return
*/
public static int getBigPriceTwo(int[] weight, int[] values, int cap) {
//特殊情况考虑
if (cap == 0 || weight.length == 0) {
return 0;
}
int[][] dp = new int[weight.length][cap + 1];
//遍历数组
//这里我选择的先遍历背包的容量 ，再去遍历物品的重量
for (int j = 1; j < cap + 1; j++) {
System.out.println("背包容量j=" + j);
for (int i = 0; i < weight.length; i++) {
//开始比较背包的容量和物品i的重量
if (j < weight[i]) {
if (i == 0) {
dp[0][j] = 0;
System.out.println(" 不放--初始化---宝石=" + ((char) (97 + i)) + "，最大的价值=dp[" + ((char) (97 + i)) + "][" + j + "]=" + dp[i][j]);
} else {
//此时物品放不进去，直接去没放进去之前的价值
dp[i][j] = dp[i - 1][j];
System.out.println(" 不放--宝石=" + ((char) (97 + i)) + "，最大的价值=dp[" + ((char) (97 + i)) + "][" + j + "]=" + dp[i][j]);
}
} else {
if (i == 0) {
dp[0][j] = values[0];
System.out.println(" 放--初始化--宝石=" + ((char) (97 + i)) + "，最大的价值=dp[" + ((char) (97 + i)) + "][" + j + "]=" + dp[i][j]);
} else {
//现在物品i是可以放进去的，那么就需要把当前的价值和上一个放进去的物品（也就是物品i-1放进去的时候）的价值做比较，谁大就取谁
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + values[i]);
//位了打印语句加放入判断
System.out.println("-----");
System.out.println(" ｜｜放宝石=" + ((char) (97 + i)) + "，最大的价值=" + (dp[i - 1][j - weight[i]] + values[i])
+ "｜｜不放" + "，最大的价值=" + (dp[i - 1][j]));
if ((dp[i - 1][j]) > (dp[i - 1][j - weight[i]] + values[i])) {
System.out.println(" ｜｜----所以不放--宝石=" + ((char) (97 + i)) + "，最大的价值=dp[" + ((char) (97 + i)) + "][" + j + "]=" + dp[i][j]);
} else {
System.out.println(" ｜｜---------所以放--宝石=" + ((char) (97 + i)) + "，最大的价值=dp[" + ((char) (97 + i)) + "][" + j + "]=dp[" + ((char) (97 + i - 1)) + "][" + (j - weight[i]) + "]+value[" + ((char) (97 + i)) + "]=" + (dp[i - 1][j - weight[i]]) + "+" + values[i] + "=" + (dp[i - 1][j - weight[i]] + values[i]));
}
}
}
}
}
return dp[weight.length - 1][cap];
}
//测试
public static void main(String[] args) {
int[] weight = {2,2,6,5,4};
int[] value = {6,3,5,4,6};
int bagSize = 8;
getBigPriceTwo(weight,value,bagSize);
}
输出结果：
背包容量j=1
不放--初始化---宝石=a，最大的价值=dp[a][1]=0
不放--宝石=b，最大的价值=dp[b][1]=0
不放--宝石=c，最大的价值=dp[c][1]=0
不放--宝石=d，最大的价值=dp[d][1]=0
不放--宝石=e，最大的价值=dp[e][1]=0
此结果可以和上面的推导联合着看------------------
背包容量j=2
放--初始化--宝石=a，最大的价值=dp[a][2]=6
-----
｜｜放宝石=b，最大的价值=3｜｜不放，最大的价值=6
｜｜----所以不放--宝石=b，最大的价值=dp[b][2]=6
不放--宝石=c，最大的价值=dp[c][2]=6
不放--宝石=d，最大的价值=dp[d][2]=6
不放--宝石=e，最大的价值=dp[e][2]=6
背包容量j=3
放--初始化--宝石=a，最大的价值=dp[a][3]=6
-----
｜｜放宝石=b，最大的价值=3｜｜不放，最大的价值=6
｜｜----所以不放--宝石=b，最大的价值=dp[b][3]=6
不放--宝石=c，最大的价值=dp[c][3]=6
不放--宝石=d，最大的价值=dp[d][3]=6
不放--宝石=e，最大的价值=dp[e][3]=6
背包容量j=4
放--初始化--宝石=a，最大的价值=dp[a][4]=6
-----
｜｜放宝石=b，最大的价值=9｜｜不放，最大的价值=6
｜｜---------所以放--宝石=b，最大的价值=dp[b][4]=dp[a][2]+value[b]=6+3=9
不放--宝石=c，最大的价值=dp[c][4]=9
不放--宝石=d，最大的价值=dp[d][4]=9
-----
｜｜放宝石=e，最大的价值=6｜｜不放，最大的价值=9
｜｜----所以不放--宝石=e，最大的价值=dp[e][4]=9
此结果和上面的推导完全一致。
5.总结
在做这种动态规划题的时候，一般是分为五个步骤来进行处理。
-
确定dp数组的含义
-
本题dp数组含义说明：
dp【i】【j】表示处理第i个物品后，此时背包重量为j，价值为dp; dp【i】【j】可以由两个状态得到：dp【i-1】【j】 和 dp【i-1】[j-weight【i】]。第一种情况，处理完i-1个物品后，背包容量已经达到了j，说明还没轮到考虑i，背包重量已经达到要求，此时无法放入i（不让处理i之后的背包重量就不是j了），价值直接继承dp【i】【j】;第二种情况，处理完i-1后，背包重量刚好是j-weight【i】，诶，这时候我放入i，背包重量刚好达到要求j，这就是为什么第二种情况要是j-weight【i】的原因。取放入或不放入的最大值，就可以得到该状态下的最大价值。
-
-
确定递推公式
- dp【i】【j】= Math.max( dp【i-1】【j】,dp【i-1】【j-weight【i】】+value【i】);
-
确认初始化的值
- 初始化当物品0在每个背包容量的最大价值
-
遍历dp数组
-
打印dp数组
