一 问题

给定 N 种物品和一个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。(每种物品只有一个)
如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

假设背包重量不能超过20，从下面几个商品中挑出一个价值最大的解

编号	价值	重量
1	3	2
2	4	3
3	5	4
4	8	5
5	10	9

问题就不多解释了，这个问题是用动态规划来做的。
动态规划三要素：

1. 状态转移方程
2. 最优子结构
3. 边界条件

参考：https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg

一般只有这3者都有，才可以用动态规划来解决问题。

二 解题思路

我们知道这种题肯定是可以用暴力枚举法来做的，但那样计算量太大了。从我们人类的角度看，很多枚举情况都是无意义的。

我们可以肯定的是有一种最优解的情况。假设我们称这种情况为Optimal.
那无论是哪种情况(包括Optimal)对各个商品无非就存在两种可能，拿或没拿

我们定义一个表达式F（N，W）
这个表单式代表的意义：对前N个商品进行挑选，背包容量为W场景下的最优解。
比如：F(4,12)，表示当可选的商品有4种（1-4），背包容量为12下的最优解。

那我们本题的最优解已经出来了：F(5,20)

那接下来怎么解呢？
我们对F(N,W)的解题思路：分析N号lin商品有没有拿的情况下的各自最优解。然后取最大值。
什么意思呢？
以F(5,20)为例Optimal情况下，5号商品没拿，那F(5,20)=F(4,20);如果5号商品拿了，那就是F(5,20)=F(4,20-w[5])+v[5]=F(4,11)+10.Optimal到底是哪种情况呢，当然是将前面的两者比较，价值比较大的情况就是Optimal。

问题：为什么只分析5号商品有没有拿，不是所有的商品都有2种情况吗？

理解：一步一步来，我们每次只分析一个商品有没有拿的情况。下一步，分析另一个商品有没有拿的情况。可以肯定地是：最后所有的商品有且都只会分析到一次

那根据上面的分析：我们也得出了状态转移方程
b站视频链接

image.png

最后边界条件

F（N，W）种的N或W只要一个为0，整个值必为0.

如何实现

一般都是画一个图表，把图表填满，就的到解了。java种一般用2维数组表示图表

image.png

public class knapsack {
    
//  private int[] weights = {2,3,4,5,9};
//  private int[] values = {3,4,5,8,10};
    
    private int[] weights = {9,4,5,2,3};
    private int[] values = {10,5,8,3,4};
    
//  int maxWeight = 20;
    
    private int[][] results = new int[6][21];
    
    
    public void knapsack() {
        for(int i = 1;i<=values.length;i++) {//行表示几个元素可能是解的一部分
            for(int j = 1;j<=20;j++) {//列代表容量，列的下标也就是每列的最大重量限制
                int value = 0;
                if(j<weights[i-1]) {
                    value= results[i-1][j];
                }else {
                    //results下标减一表示的是
                    value = results[i-1][j]>results[i-1][j-weights[i-1]]+values[i-1]?results[i-1][j]:results[i-1][j-weights[i-1]]+values[i-1];

                }
                
                results[i][j] = value;
            }
        }
        
    }
    
    public static void main(String[] args) {
        knapsack k = new knapsack();
        k.knapsack();
        for(int[] subResults:k.results) {
            int index = 0;
            for(int v:subResults) {
                System.out.print(v);
                if(index == 20) {
                    System.out.println();
                }else {
                    System.out.print("\t");
                }
                index++;
            }
        }
    }

}

问题：商品序号必须是按某个属性升序吗？

经上面代码测试，没要求。这也复合常理，只要我们对每个商品都进行了拿或不拿的情况分析，那就ok了。