【动态规划】完全背包、多重背包

素颜马尾好姑娘i 2022-08-09 14:59 182阅读 0赞

## **完全背包** ##

### **问题** ###

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

### **解析** ###

动态规划解：  
dp\[i\]\[j\]是：在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值；  
状态转移方程：  
`dp[i][v]=max{ f[i-1][v-k*c[i]]+k*w[i] | 0 <= k*c[i] <= v}`  
但是，这里并不能在常数时间内求出k。所以，我们需要寻求更好的办法解决，通过查阅一般有两种方法优化，一种是转化成01背包问题（还是很麻烦），另一种是O（VN）的解法，这里我介绍后面一种。

### **实现** ###

for (int i = 1; i <= N; i++)
         for (int v = 0; v <= V; v++)
             f[v] = max(f[v], f[v - c[i]] + w[i]);

**仔细看你会发现这个跟01背包空间优化后的的代码只有V的循环次数不同。因为01背包中要保证第i次循环中的状态f\[i\]\[v\]是由状态f\[i-1\]\[v-c\[i\]\]递推而来的。而完全背包相反：现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f\[i\]\[v-c\[i\]\]，所以就可以并且必须采用v=0..V的顺序循环。**

## **多重背包** ##

### **问题** ###

有N种物品和一个容量为V的背包。第i种物品最多有n\[i\]件可用，每件费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

### **解析** ###

这题目和上面的完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n\[i\]+1种策略：取0件，取1件……取n\[i\]件。令f\[i\]\[v\]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：  
`f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}`  
同时，问题也和完全背包一样，过于复杂！

同样，可以转换成01背包问题和O(VN)的时间复杂度解决，但是，非常复杂，在此贴出一个较好的解法，参考而已。

#include <iostream>
    using namespace std;
    
    int nCases;
    int nValue, nKind;
    int value[105], weight[105], bag[105];
    int nMultiplePack[105];
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
        scanf("%d", &nCases);
        while(nCases--)
        {
            memset(nMultiplePack, 0, sizeof(nMultiplePack));
            scanf("%d %d", &nValue, &nKind);
            for(int i=0; i<nKind; ++i)
                scanf("%d %d %d", &value[i], &weight[i], &bag[i]);
            for(int i=0; i<nKind; ++i)
                for(int j=0; j<bag[i]; ++j)
                    for(int k=nValue; k>=value[i]; --k)
                        if(nMultiplePack[k] < nMultiplePack[k-value[i]]+weight[i])
                            nMultiplePack[k] = nMultiplePack[k-value[i]] + weight[i];
            printf("%d\n", nMultiplePack[nValue]);
    
        }
        return 0;
    }