背包问题—01背包、完全背包

末蓝、 2022-05-30 10:10 507阅读 0赞

## 01背包问题 ##

### 题目 ###

有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

### 思路 ###

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。所以对于第i件物品，可以转化成与前i-1个物品相关的两个子问题：

*  如果放入第i个物品，那么当前最大的价值f(i,V)就等于将前i-1个物品放入容量为(V-Vi)的背包中能得到的最大价值f(i-1, V-Vi) 与 第i个物品的价值Wi 的和。
 *  如果不放入第i个物品，那么f(i, V)就等于将前i-1个物品放入容量为V的背包能得到的最大价值f(i-1, V)

所以递推公式为： ***F(i, V) = max(F(i-1, V), F(i-1, V-Vi) + Wi)***

有了递推公式就可以使用动态规划来对该问题求解了。

int backPack1(int m, vector<int> &V, vector<int> &W) {
            int n = V.size();
            vector<int> dp(m+1, 0);
    
            for(int i = 0; i < n; i++)
                for(int j = m; j >= 0; j--){  
                            //这里一定要逆序，正序会将之后要用到的数据提前覆盖掉
                    if(j - V[i] < 0)
                        continue;
                    dp[j] = max(dp[j - V[i]] + W[i], dp[j]);
                }
            return dp[m];
        }

## 完全背包问题 ##

### 题目 ###

完全背包和01背包的不同在于：01背包中一个物品只有一件，你只能选择拿或不拿，而在完全背包中，一个物品有无数件，只要不超过背包容量，你可以拿任意件。

### 思路 ###

在01背包的基础上我们都能得到如下的递推公式：  
***F(i, V) = max(F(i-1, V - k\*Vi) + k\*Wi | 0 <= k\*Vi <= V)***  
该公式可进一步推导为如下形式：  
***F(i, V) = max(F(i-1, V), F(i, V-Vi) + Wi)***

### 优化 ###

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j 满足 Vi < Vj 且 Wi ≥ Wj，则将可以将物品j 直接去掉，不用考虑。这个优化的正确性是显然的：任何情况下都可将价值小费用高的j 换成物美价廉的i，得到的方案至少不会更差。

下面给出代码

//优化数据
    void majorizing(int m, vector<int> &v, vector<int> &w)
    {
        int n = v.size();
        vector<int>::iterator it;
    
        for(int i = 0; i < n; i++){
            if(v[i] > m){
                v[i] = -1;
                w[i] = -1;
                continue;
            }
            for(int j = 0; j < n; j++)
                if(w[i] >= w[j] && v[i] < v[j]) {
                    v[j] = -1;
                    w[j] = -1;
                }
        }
    
        for(it = v.begin(); it != v.end(); it++)
            if(*it == -1){
                v.erase(it);
                it--;
            }
        for(it = w.begin(); it != w.end(); it++)
            if(*it == -1){
                w.erase(it);
                it--;
            }
    }
    //动态规划求解
    int backpack2(int m, vector<int> &v, vector<int> &w)
    {
        vector<int> dp(m+1, 0);
    
        majorizing(m, v, w);
    
        for(int i = 0; i < v.size(); i++)
            for(int j = 0; j <= m; j++){
                if(j >= v[i])
                    dp[j] = std::max(dp[j], dp[j-v[i]] + w[i]);
            }
        return dp[m];
    }