晚上睡不著，翻同學發(fā)出來的筆記，看到背包問題，想了一下，趁熱打鐵把思路寫下來。
如果閱讀過程中有任何地方不理解，請先記住，耐下性子往下看。

0-1背包問題：給定 n 種物品和一個容量為 C 的背包，物品 i 的重量是 w[i]，其價值為 v[i]。問：應(yīng)該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？

難點：由于給點的物品的順序是隨機的，所以有可能性價比最高的物品在后面，但按照順序裝物品，等要裝性價比高的物品時，此時我們的背包已經(jīng)填滿了。

解決思路：假如每放一個物品下去，我都能列出所有組合的物品的價值最大值，最優(yōu)解就出來了。

解決方法：
定義一個二維數(shù)組m[ i ][ j ]，i代表第i個物品，j代表此時背包的重量。而p[ i ][ j ] 代表總價值

對于第i件物品，每個j都有兩種情況
1） j < w[ i ]
由于此時背包的容量小于物品i的重量，因此 m[ i ] [ j ]=p[ i-1 ][ j ] ·······①

2）j >= w[ i ]
此時背包的容量大于等于物品i的重量，那么這時候就要比較 當物品i的價值加上之前物品的價值 是否比 之前各種物品組合的價值 大，因此m[ i ] [ j ] = max(m[ i-1 ][ j ] ，m[ i-1 ][ j - m[ i ] ]+v[ i ])

ok，我們舉個例子來說明一下會更加容易理解（這個代碼是我同學的）
我們定義：
v[7]={0,8,10,6,3,7,2}; 價值
w[7]={0,4,6 ,2,2,5,1}; 重量

#include <stdio.h>
#include <string.h>
#include <algorithm> 
using namespace std;
const int N=15;
int main(){ 
    int v[N]={0,8,10,6,3,7,2}; 
    int w[N]={0,4,6,2,2,5,1};
    int m[N][N];
    int n=6,c=12;
    memset(m,0,sizeof(m));//數(shù)組初始化為0
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            else m[i][j]=m[i-1][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            printf("%d ",m[ i ][ j ]);
        }
    printf("\n");
    }
    return 0;
}

背包問題.jpg

當我列到m[ 3 ] [ 4 ]的時候，我就知道為什么①那個地方是m[ i ] [ j ]=p[ i-1 ][ j ]，他的目的就是要將之前物品組合的所有可能的價值再列出來，為下一個做準備。
與其說j是代表此時背包的重量，倒不如說，當背包的容量為j時，可以有多少種放物品的方式。
j的不同，代表著物品組合的方式也不一樣，比如m[ 3 ][ 6 ]表示取物品1和物品3，m[ 3 ][ 8 ]表示取物品2和物品3，m[ 3 ][ 12 ]表示取物品1、2、3。

程序運行后，結(jié)果如下，為了更加方便理解，我調(diào)整了格式，最上面一排是j的值

圖片.png

這就符合每放一個物品下去，都能列出所有組合的物品的價值最大值的思路了

這種題目跟2048那幾道題有異曲同工之處，也是遞歸問題。