前言&背包问题的历史
背包问题(Knapsack problem)是一种组合优化的NP完全问题（NP完全问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P）。
背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪，早期的作品可追溯到1897年 数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品 ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
可以看到上面的图，背包问题还是很有很多种,但其实我们非竞赛人员只需要学会01背包、完全背包，最多再加上点多重背包。博主只讨论01背包和完全背包问题。
我们都知道背包问题是动态规划经典问题，但为什么不可以使用贪心思维来解决呢？我举个简单例子。
如果上面我们使用贪心思想总是去装 价值 / 物品大小 大的，即最多装价值为的16的物品，还剩余容量为3，无法再装下其他物品，这也是为什么不能用贪心去做，无法最大化的利用背包空间。
01背包
1、题目
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，求能够装入背包的最大价值是多少？
2、暴力解01背包
说起背包就会想到dp，使用动态规划的方法写，其实这也可以使用回溯算法暴力求解，大家不常用回溯算法暴力求解是因为
每件物品都存在装入和不装入两种情况，总的时间复杂度是O(2ᴺ)， 这是不可取的。但我们也可以了解了解怎么暴力求解背包问题。
还是使用以上面的例子试一试：
5 10 2 5 4 2 3 6 3 5 4 6
Ⅰ、代码
import java.util.Scanner; public class Main { static int SetCapacity=0;//背包的初始容量 static int MaxCapacity=0;//使用了背包多少容量 static int MaxValue=0;//最大价值 static void method(int[][] arr,int k,int capacity,int value){ for (int i=k;i<arr.length;i++){ if (SetCapacity-capacity>=arr[i][0]){//判断当前背包的剩余容量是否可以装下第i个物品 capacity+=arr[i][0]; value+=arr[i][1]; method(arr,i+1,capacity,value); //回溯 capacity-=arr[i][0]; value-=arr[i][1]; }else{//如果不行,则跳过第i个物品，继续递归后面的物品，看是否可以装下。 if (capacity>=SetCapacity)//如果背包装不下了，则退出循环，返回上一次递归 break; method(arr,i+1,capacity,value); } } if (value>MaxValue){ MaxValue=value; MaxCapacity=capacity; } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); SetCapacity=sc.nextInt(); int[][] arr=new int[n][2]; for (int i=0;i<n;i++){//物品大小 arr[i][0]=sc.nextInt(); } for (int i=0;i<n;i++){//物品价值 arr[i][1]=sc.nextInt(); } method(arr,0,0,0); System.out.println(MaxCapacity+" "+MaxValue);//9 17 } }
3、动态规划解01背包
Ⅰ、二维dp数组解01背包
1）dp数组的含义
可能很多人会写动态规划的题目，会写01背包，但是很多人却不会去注重思考dp数组的含义，其代表着什么？01背包的dp数组含义是：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
不懂可以看看下面图，仔细想想。
2）递推公式
dp[i][j]=Max( dp[i-1][j] , dp[i-1][ j-wᵢ ]+vᵢ )
dp[i][j]我们在上面知道 这 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。此时我们应该考虑下标为i物品是否放入背包（先要考虑j-wᵢ是否大于等于0，即此时是否能够放入物品i ），于是就有两种情况：放 或者 不放。
不放物品i就是dp[i-1][j]嘛，放物品i就是容量为j的背包需要留出这个物品i的容量才可以放物品i，即dp[i-1][ j-wᵢ ],而这又是下标为 0到 i-1 的物品里任意取，放进容量为 j-wᵢ 的背包，最大的价值总和。然后再由 dp[i-1][ j-wᵢ ]+vᵢ 就是dp[i][j]放物品 i 的最大价值。
然后 取 Max( dp[i-1][j] , dp[i-1][ j-wᵢ ]+vᵢ ) 二者的最大值。
3）dp数组的初始化
我们由上面知道了求 dp[i][j] 需要知道 dp[i-1][j]和 dp[i-1][ j-wᵢ ]+vᵢ ，即需要先知道上图红色箭头所指的位置，这样我们便清楚知道了，dp数组应该如何初始化，即绿色箭头所指的列和行。
初始化如下图：
dp数组初始化了，递推公式我们也知道了，后面这个数组自然而然也可以求出来了。
4）遍历顺序的讨论
上面我们得出dp数组是先遍历物品，再遍历背包容量，那可不可以先遍历背包容量再遍历物品，答案是可以的，但此时 dp[j][i] =Max( dp[ j-wᵢ ][ i-1 ]+vᵢ ,dp[ j ][ i-1 ] )。
而此时 dp数组的含义就是 容量为 j 的背包随机放 0-i 之间的物品，所放物品的最大价值。
5、代码
以先遍历物品，在遍历背包为例
public class Main { public static void main(String[] args) { int[] weight = {1,3,4}; int[] value = {3,4,6}; int bagSize = 4; method(weight,value,bagSize); } /** * 动态规划获得结果 * @param weight 物品的重量 * @param value 物品的价值 * @param bagSize 背包的容量 */ public static void method(int[] weight, int[] value, int bagSize){ // 创建dp数组 int goods = weight.length; // 获取物品的数量 int[][] dp = new int[goods][bagSize + 1]; // 初始化dp数组 // 创建数组后，其中默认的值就是0 for (int j = weight[0]; j <= bagSize; j++) { dp[0][j] = value[0]; } // 填充dp数组 for (int i = 1; i < weight.length; i++) { for (int j = 1; j <= bagSize; j++) { if (j < weight[i]) { /** * 当前背包的容量都没有当前物品i大的时候，是不放物品i的 * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值 */ dp[i][j] = dp[i-1][j]; } else { /** * 当前背包的容量可以放下物品i * 那么此时分两种情况： * 1、不放物品i * 2、放物品i * 比较这两种情况下，哪种背包中物品的最大价值最大 */ dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]); } } } // 打印dp数组 for (int i = 0; i < goods; i++) { for (int j = 0; j <= bagSize; j++) { System.out.print(dp[i][j] + "\t"); } System.out.println(); } } }
输出
1. 0 3 3 3 3 2. 0 3 3 4 7 3. 0 3 3 4 7
