背包问题

0-1背包问题

学习的教程是 https://github.com/tianyicui/pack/blob/master/V2.pdf ，讲得非常好，层层深入，在此向作者致谢。

基本思路

乍一看上去，这部分的思路和前面最短路的 floyd 算法特别像。都是 dp，列出状态转移方程，在不冲突的情况下把空间复杂度降一个维度。

在这里，先用一个二维数组 f[i][v] 定义允许前 i 件物品放入容量为 v 的背包中时，最大的价值。状态转移方程就是：f[i][v] = max{f[i - 1][v], f[i - 1][v - cost[i]] + value[i]}。

即，如果第 i 件物品放入，剩余空间就是个更小的背包了，产生的价值就是“允许前 i - 1 件物品放入容量为 v - cost[i]的背包产生的价值”，加上第 i 件物品的价值。若不放入，则价值直接是f[i - 1][v]。

对于这个二维数组，只要内层循环 v 外层循环 i 就可以了。

压缩空间

简化到两个一维数组当然是可行的，但是一个一维数组会不会也可以呢？

是的，而且比 floyd 里面的证明简单多了。对于上一篇 floyd 而言，迭代到 k 的时候， 想要取的dist[i][k]和dist[k][j]都不知道是旧值还是迭代值，需要证明即使是迭代值，也不影响最终的结果。

而这里就很明显，由于我们取的第二个维度是v - cost[i]小于 v , 即我们拿的总是数组这一行中更靠前的值，因此只要让 v 这一层从后向前循环，我们每次拿到的必定是还没修改的旧值。（想拿迭代值也简单，从前向后循环即可）

装得下还是必须装满

如果要求装得下即可，那么初始化时应该全部置为 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]。

基本思路

可以在循环到f[i][v]时，对放入 0、1、2... 件都试一试。其实前面的 0 - 1背包问题也可以纳入这个框架，max{f[i - 1][v], f[i - 1][v - cost[i]] + value[i]}中这两项正是放入 0 个和 1 个的情况。（也可以在外层循环修改，把“放 k 个物品 i ” 看作 “有 k 个物品，它们的 cost 和 value 正好和物品 i 的相同”。）

代码写成了这样，只有循环最内部多了一层循环：

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] 倍的提升的。然而，只要改变内层循环的方向，就可以直接在原来的复杂度下解决！

相比于void knapsack_01，只有 j 的循环方向改变为从前向后：

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");
}

道理就在于，状态转移方程是：f[i][v] = max{f[i - 1][v], f[i][v - cost[i]] + value[i]}。
很喜欢教程作者的这一段说明：

为什么这个算法就可行呢？首先想想为什么 01 背包中要按照 v 递减的次序来循环。让 v 递减是为了保证第 i 次循环中的状态 F [i; v] 是由状态 F [i − 1; v − Ci] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果 F [i − 1; v − Ci]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却正需要一个可能已选入第 i 种物品的子结果 F [i; v − Ci]，所以就可以并且必须采用递增的顺序循环。这就是这个简单的程序为何成立的道理。

多重背包问题

对每一个物品指定件数，就成了多重背包问题。很明显，类似完全背包问题的基本解法，完全可以转化成 0 - 1 背包问题。

一个降低复杂度的方法是将 k 个物品分成 1、2、4... (k-1-2-4...) 件物品的分别打包，如13 = 1 + 2 + 4 + 6。这样分的结果是对于任意 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 的数量。

• 如果这个填充是不可行的，那么置为 -1。
• 如果f[i][j]大于等于 0 ,就可以认定这个填充由前 i 种硬币来完成是可行的。
• 进一步，大于 0，则意味着完成填充后，最多还可以剩下一些硬币 i ，当然，这些多余的硬币意味着我们还可以拿它去填充更大的金额。

使用二维数组的代码如下，让我自己想的话，估计打死也想不出来：

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){ //如果用前面的硬币就已经可行了
                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");
    }
}

这个二维数组是超了内存限制的，幸而，这个写在一维数组里是不会冲突的。于是这道题 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){ //如果用前面的硬币就已经可行了
                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;
}