一 問題

給定 N 種物品和一個容量為 V 的背包，物品 i 的體積是 wi，其價值為 ci 。(每種物品只有一個)
如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？

假設(shè)背包重量不能超過20，從下面幾個商品中挑出一個價值最大的解

問題就不多解釋了，這個問題是用動態(tài)規(guī)劃來做的。
動態(tài)規(guī)劃三要素：

1. 狀態(tài)轉(zhuǎn)移方程
2. 最優(yōu)子結(jié)構(gòu)
3. 邊界條件

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

一般只有這3者都有，才可以用動態(tài)規(guī)劃來解決問題。

二 解題思路

我們知道這種題肯定是可以用暴力枚舉法來做的，但那樣計算量太大了。從我們?nèi)祟惖慕嵌瓤?，很多枚舉情況都是無意義的。

我們可以肯定的是有一種最優(yōu)解的情況。假設(shè)我們稱這種情況為Optimal.
那無論是哪種情況(包括Optimal)對各個商品無非就存在兩種可能，拿或沒拿

我們定義一個表達式F（N，W）
這個表單式代表的意義：對前N個商品進行挑選，背包容量為W場景下的最優(yōu)解。
比如：F(4,12)，表示當(dāng)可選的商品有4種（1-4），背包容量為12下的最優(yōu)解。

那我們本題的最優(yōu)解已經(jīng)出來了：F(5,20)

那接下來怎么解呢？
我們對F(N,W)的解題思路：分析N號lin商品有沒有拿的情況下的各自最優(yōu)解。然后取最大值。
什么意思呢？
以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到底是哪種情況呢，當(dāng)然是將前面的兩者比較，價值比較大的情況就是Optimal。

問題：為什么只分析5號商品有沒有拿，不是所有的商品都有2種情況嗎？

理解：一步一步來，我們每次只分析一個商品有沒有拿的情況。下一步，分析另一個商品有沒有拿的情況。可以肯定地是：最后所有的商品有且都只會分析到一次

那根據(jù)上面的分析：我們也得出了狀態(tài)轉(zhuǎn)移方程
b站視頻鏈接

image.png

最后邊界條件

F（N，W）種的N或W只要一個為0，整個值必為0.

如何實現(xiàn)

一般都是畫一個圖表，把圖表填滿，就的到解了。java種一般用2維數(shù)組表示圖表

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++) {//列代表容量，列的下標(biāo)也就是每列的最大重量限制
                int value = 0;
                if(j<weights[i-1]) {
                    value= results[i-1][j];
                }else {
                    //results下標(biāo)減一表示的是
                    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++;
            }
        }
    }

}

問題：商品序號必須是按某個屬性升序嗎？

經(jīng)上面代碼測試，沒要求。這也復(fù)合常理，只要我們對每個商品都進行了拿或不拿的情況分析，那就ok了。