01背包算法

示例归纳代码 01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章就是从一个小白的角度来理解01背包算法，因为我也是从小白过来的。

有的文章一开头先扔个公式，一看就懵逼了。所以先搞懂这个过程是在干什么。 先用一个简单的例子来进行讲解

比如现在有四个物品，要把这四个物品放入一个容量为8的背包之中，然后现在要求这个背包最大能够放入价值为多少的物品？

示例

接下来第一件事就是列表，不要问为什么，就是这个方法，这张表是至底向上，从左到右生成的。

首先第一行第一列 因为背包容量为0无法放入物品所以第一列的最大价值就全为0； 物体编号为0意味着放入前0个物品，也就是不放入物品，所以第一行的最大价值就全为0

填写第一行 填写第二行 以此类推写完全部 拿最后一个举例看看背包内价值最大的情况下，背包内装了哪些物品

归纳

解法归纳： 一、如果装不下当前物品 那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样的。

二、如果装得下当前物品 假设1： 装当前物品，在给当前物品预留了相应空间的情况下，前n-1个物品的最佳组合加上当前的价值就是总价值

假设2： 不装当前物品，那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样的。 选取假设1和假设2中的较大的价值，为当前的最佳组合的价值。

如果你看懂了以上的所有的流程，那现在下面这个式子就可以理解了。 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。

回溯： 从表的右下角开始回溯，如果发现前n个物品最佳组合的价值和前n-1个物品最佳组合的价值一样，说明第n个物品没有被装入，否则第n个物品被装入

代码

public class OneZeroBag { //此处不考虑第一行和第一列都为0的情况，所以下标直接从1开始，数组开辟也多加1 public static int solution(int W, int N, int[] weights, int[] values){ int[][] map = new int[W+1][N+1]; //定义二维数组 W表示容量行 N表示数量的列 for (int i = 1; i <= N ; i++) { int value = values[i-1];//取当前物品的的价值 int weight = weights[i-1];//取当前物品的容量 for (int j = 1 ; j <= W ; j++) { if(j < weight){ //剩余容量不足以放入最后一个 map[j][i] = map[j][i-1]; continue; } //取放入和不放入两个的价值的较大值 map[j][i] = Math.max(map[j-weight][i-1]+value,map[j][i-1]); } } int a = map[W][N]; return a; } public static void main(String[] args) { //物品的重量 int[] weight = {2,3,4,5}; //物品价值 int[] value = {3,4,5,6}; //背包容量 int BagWeight = 8; //物品数量 int Num = 4; System.out.println("最大价值为："+solution(8,4,weight,value)); } } 最大价值为：10