0-1背包問題

學習的教程是 https://github.com/tianyicui/pack/blob/master/V2.pdf ，講得非常好，層層深入，在此向作者致謝。

基本思路

乍一看上去，這部分的思路和前面最短路的 floyd 算法特別像。都是 dp，列出狀態(tài)轉(zhuǎn)移方程，在不沖突的情況下把空間復雜度降一個維度。

在這里，先用一個二維數(shù)組 f[i][v] 定義允許前 i 件物品放入容量為 v 的背包中時，最大的價值。狀態(tài)轉(zhuǎn)移方程就是：f[i][v] = max{f[i - 1][v], f[i - 1][v - cost[i]] + value[i]}。

即，如果第 i 件物品放入，剩余空間就是個更小的背包了，產(chǎn)生的價值就是“允許前 i - 1 件物品放入容量為 v - cost[i]的背包產(chǎn)生的價值”，加上第 i 件物品的價值。若不放入，則價值直接是f[i - 1][v]。

對于這個二維數(shù)組，只要內(nèi)層循環(huán) v 外層循環(huán) i 就可以了。

壓縮空間

簡化到兩個一維數(shù)組當然是可行的，但是一個一維數(shù)組會不會也可以呢？

是的，而且比 floyd 里面的證明簡單多了。對于上一篇 floyd 而言，迭代到 k 的時候， 想要取的dist[i][k]和dist[k][j]都不知道是舊值還是迭代值，需要證明即使是迭代值，也不影響最終的結(jié)果。

而這里就很明顯，由于我們?nèi)〉牡诙€維度是v - cost[i]小于 v , 即我們拿的總是數(shù)組這一行中更靠前的值，因此只要讓 v 這一層從后向前循環(huán)，我們每次拿到的必定是還沒修改的舊值。（想拿迭代值也簡單，從前向后循環(huán)即可）

裝得下還是必須裝滿

如果要求裝得下即可，那么初始化時應該全部置為 0，表示不允許任何物品裝入的時候就只能是 0 的價值了。我寫的代碼核心部分如下：

void knapsack_01(int ans[]){ //不必裝滿
    ans[0] = 0;
    for(int i = 1; i <= V; i ++) ans[i] = 0;

    for(int i = 0; i <= N; i ++){ //允許裝前 i 件物品
        for(int j = V; j >= cost[i]; j --){ //從后向前
            ans[j] = max(ans[j], ans[j - cost[i]] + value[i]);
        }
    }

    for(int i = 0; i <= V; i ++) printf("%d ", ans[i]);
    printf("\n");
}

如果要求裝滿，除了f[0] = 0外，其余都置為 -Inf。這一步是可以理解的，后面每一步中若不是裝滿，值都會是 -Inf。具體證明我偷懶沒有做，就信了吧。

代碼如下，只有第三行初始化不同。

void knapsack_01_full(int ans[]){ //必須裝滿
    ans[0] = 0;
    for(int i = 1; i <= V; i ++) ans[i] = -(1 << 29); //只有初始化的不同

    for(int i = 0; i <= N; i ++){ //允許裝前 i 件物品
        for(int j = V; j >= cost[i]; j --){ //從后向前
            ans[j] = max(ans[j], ans[j - cost[i]] + value[i]);
        }
    }

    for(int i = 0; i <= V; i ++) printf("%d ", ans[i]);
    printf("\n");    
}

完全背包問題

每件物品裝多少次都可以，不過再多也不會多過 v / cost[i]。

基本思路

可以在循環(huán)到f[i][v]時，對放入 0、1、2... 件都試一試。其實前面的 0 - 1背包問題也可以納入這個框架，max{f[i - 1][v], f[i - 1][v - cost[i]] + value[i]}中這兩項正是放入 0 個和 1 個的情況。（也可以在外層循環(huán)修改，把“放 k 個物品 i ” 看作 “有 k 個物品，它們的 cost 和 value 正好和物品 i 的相同”。）

代碼寫成了這樣，只有循環(huán)最內(nèi)部多了一層循環(huán)：

void knapsack_complete(int ans[]){ //完全背包問題
    ans[0] = 0;
    for(int i = 1; i <= V; i ++) ans[i] = 0;

    for(int i = 0; i <= N; i ++){ //物品 i
        for(int j = V; j >= cost[i]; j --){ //從后向前
            for(int k = 0; k * cost[i] <= j; k ++)
                ans[j] = max(ans[j], ans[j - k * cost[i]] + k * value[i]);
        }
    }

    for(int i = 0; i <= V; i ++) printf("%d ", ans[i]);
    printf("\n");
}

巧妙的寫法

這個復雜度比起 0 - 1 背包問題來，是有一個 平均v / cost[i] 倍的提升的。然而，只要改變內(nèi)層循環(huán)的方向，就可以直接在原來的復雜度下解決！

相比于void knapsack_01，只有 j 的循環(huán)方向改變?yōu)閺那跋蚝螅?/p>

void knapsack_complete_quick(int ans[]){ //完全背包問題復雜度降低的做法
    ans[0] = 0;
    for(int i = 1; i <= V; i ++) ans[i] = 0;

    for(int i = 0; i <= N; i ++){ //允許裝前 i 件物品
        for(int j = cost[i]; j <= V; j ++){ //從前向后
            ans[j] = max(ans[j], ans[j - cost[i]] + value[i]);
        }
    }

    for(int i = 0; i <= V; i ++) printf("%d ", ans[i]);
    printf("\n");
}

道理就在于，狀態(tài)轉(zhuǎn)移方程是：f[i][v] = max{f[i - 1][v], f[i][v - cost[i]] + value[i]}。
很喜歡教程作者的這一段說明：

為什么這個算法就可行呢？首先想想為什么 01 背包中要按照 v 遞減的次序來循環(huán)。讓 v 遞減是為了保證第 i 次循環(huán)中的狀態(tài) F [i; v] 是由狀態(tài) F [i ? 1; v ? Ci] 遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第 i 件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第 i 件物品的子結(jié)果 F [i ? 1; v ? Ci]。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第 i 種物品”這種策略時，卻正需要一個可能已選入第 i 種物品的子結(jié)果 F [i; v ? Ci]，所以就可以并且必須采用遞增的順序循環(huán)。這就是這個簡單的程序為何成立的道理。

多重背包問題

對每一個物品指定件數(shù)，就成了多重背包問題。很明顯，類似完全背包問題的基本解法，完全可以轉(zhuǎn)化成 0 - 1 背包問題。

一個降低復雜度的方法是將 k 個物品分成 1、2、4... (k-1-2-4...) 件物品的分別打包，如13 = 1 + 2 + 4 + 6。這樣分的結(jié)果是對于任意 m (0 < m <= k) 個物品，都可以看作幾個這些打包物品的和。這樣在復雜度上，將 k 降低到了 log(k) 。

O(V * N)的多重背包問題

問題是“每種有若干件的物品能否填滿給定容量的背包”，即要求填滿，且只管可行性，不用考慮價值最大化。我傾向于認為這個問題和前面的問題是有一定差別的。

題目

杭電2844就是一道標準的這樣的問題：

Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.

You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

用f[i][j]表示在允許使用前 i 種硬幣去填補總量為 j 的金額時，最多剩余的硬幣 i 的數(shù)量。

• 如果這個填充是不可行的，那么置為 -1。
• 如果f[i][j]大于等于 0 ,就可以認定這個填充由前 i 種硬幣來完成是可行的。
• 進一步，大于 0，則意味著完成填充后，最多還可以剩下一些硬幣 i ，當然，這些多余的硬幣意味著我們還可以拿它去填充更大的金額。

使用二維數(shù)組的代碼如下，讓我自己想的話，估計打死也想不出來：

void knapsack(){
    //初始化，除了價格為0可行，其它都不可行
    f[0][0] = 0;
    for(int i = 1; i <= m; i ++) f[0][i] = -1;

    for(int i = 1; i <= n; i ++){ //用前i種硬幣
        for(int j = 0; j <= m; j ++){
            if(f[i - 1][j] >= 0){ //如果用前面的硬幣就已經(jīng)可行了
                f[i][j] = num[i]; //硬幣i可以不用，剩下num[i]個
            }else{
                f[i][j] = -1;
            }
        }
        for(int j = 0; j + cost[i] <= m; j ++){
            if(f[i][j] > 0) //如果還剩下一些硬幣i，就可以去形成后面更高的金額
                f[i][j + cost[i]] = max(f[i][j + cost[i]], f[i][j] - 1); //拿出一個硬幣i，形成金額j + cost[i]
        }
        // for(int j = 0; j <= m; j ++) printf("%d ", f[i][j]);
        // printf("\n");
    }
}

這個二維數(shù)組是超了內(nèi)存限制的，幸而，這個寫在一維數(shù)組里是不會沖突的。于是這道題 AC 的代碼如下：

#include <cstdio>
#include <cstdlib>

#define max(x, y) ((x) > (y)? (x): (y))

const int maxN = 100, maxM = 100000;
int f[maxM + 1]; 
int cost[maxN + 1], num[maxN + 1];
int n, m, nPrice;

void knapsack(){
    //初始化，除了價格為0可行，其它都不可行
    f[0] = 0;
    for(int i = 1; i <= m; i ++) f[i] = -1;

    for(int i = 1; i <= n; i ++){ //用前i種硬幣
        for(int j = 0; j <= m; j ++){
            if(f[j] >= 0){ //如果用前面的硬幣就已經(jīng)可行了
                f[j] = num[i]; //硬幣i可以不用，剩下num[i]個
            }else{
                f[j] = -1;
            }
        }
        for(int j = 0; j + cost[i] <= m; j ++){
            if(f[j] > 0) //如果還剩下一些硬幣i，就可以去形成后面更高的金額
                f[j + cost[i]] = max(f[j + cost[i]], f[j] - 1); //拿出一個硬幣i，形成金額j + cost[i]
        }
    }
}

int main(){
    while(scanf("%d %d", &n, &m) == 2){
        if(n == 0 && m == 0) break;
        for(int i = 0; i < n; i ++) scanf("%d", cost + i + 1);
        for(int i = 0; i < n; i ++) scanf("%d", num + i + 1);
        
        knapsack();

        nPrice = 0;
        for(int i = 1; i <= m; i ++) if(f[i] >= 0) nPrice ++;
        printf("%d\n", nPrice);       
    }

    return 0;
}