背包九讲

798236606

测试平台：https://www.acwing.com/problem/

1.01背包

解：

二维DP

dp[j]表示前i个物品在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp[0]必须初始化为0（因为前0个物品的价值量肯定为0）

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

int n, m;
int dp[maxn][maxn];

int main(void)
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i)
    {
        int v, w;
        
        cin >> v >> w;
        
        for (int j = 0; j <= m; ++j)//如果装不下，则继承i - 1的结果,若装的下则考虑装与不装哪个更赚
            dp[i][j] = (j < v) ? dp[i - 1][j] : max(dp[i - 1][j], dp[i - 1][j - v] + w);
    }
    
    cout << dp[n][m] << endl;

    return 0;
}

【注】大多数一维DP做起来很困难，此时升到二维会简单很多

一维DP

dp[j]表示当前物品与之前的物品（其实还是前i个物品）在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp必须初始化为0（因为前0个物品的价值量肯定为0）

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

int n, m;
int dp[maxn];

int main(void)
{
    cin >> n >> m;
    
    while (n--)
    {
        int v, w;
        
        cin >> v >> w;

        //装不下的情况不用管，会自然地继承上一次的计算结果，每次计算只是对上次计算的加工处理。j从后往前保证每个物品只被计算一次
        for (int j = m; j >= v; --j) dp[j] = max(dp[j], dp[j - v] + w);
    }
    
    cout << dp[m] << endl;

    return 0;
}

2.完全背包

解：

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

int n, m;
int dp[maxn];

int main(void)
{
    cin >> n >> m;
    
    while (n--)
    {
        int v, w;
        
        cin >> v >> w;

        //j从前往后保证每个物品可以被计算多次
        for (int j = v; j <= m; ++j) dp[j] = max(dp[j], dp[j - v] + w);
    }
    
    cout << dp[m] << endl;

    return 0;
}

其实还有一种更容易想到的解法：枚举每件物品的选取个数（其实把问题转化成了01背包）

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

int n, m;
int dp[maxn];

int main(void)
{
    cin >> n >> m;
    
    while (n--)
    {
        int v, w;
        
        cin >> v >> w;

        for (int j = m; j >= v; --j) 
            for (int k = 1; k * v <= j; ++k)
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    
    cout << dp[m] << endl;

    return 0;
}

3.多重背包Ⅰ

解:

类似于上一题的第二种解法

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e2 + 10;

int n, m;
int dp[maxn];

int main(void)
{
    cin >> n >> m;
    
    while (n--)
    {
        int v, w, t;
        
        cin >> v >> w >> t;

        for (int j = m; j >= v; --j) 
            for (int k = 1; k <= t && k * v <= j; ++k)
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    
    cout << dp[m] << endl;

    return 0;
}

但是当数据较大时效率就会比较差，此时使用二进制优化法

4.多重背包Ⅱ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 2e3 + 5;

typedef struct GOOD{
    int v, w;
    
    GOOD (int _v, int _w) : v(_v), w(_w) {};
}Good;

int n, m;
int dp[maxn];
vector<Good> goods;

int main(void)
{
    cin >> n >> m;
    
    while (n--)
    {
        int v, w, t;
        
        cin >> v >> w >> t;
        
        for (int k = 1; k <= t; t -= k, k *= 2)
            goods.push_back(GOOD(k * v, k * w));
            
        if (t) goods.push_back(GOOD(t * v, t * w));
    }
    
    for (auto good: goods)
        for (int j = m; j >= good.v; --j)
            dp[j] = max(dp[j], dp[j - good.v] + good.w);
    
    cout << dp[m] << endl;
    
    return 0;
}

未完待续。。。

ming@1993

多谢！