背包问题

背包问题：

1. 01背包
2. 完全背包
3. 多重背包
4. 分组背包
5. 混合背包
6. 二维费用背包
7. 有依赖的背包问题
8. 背包问题求方案数
9. 背包问题求具体方案

01背包

基本内容

特点

每个物品只有一件, 选择与不选择

状态表示

\(dp[i][j]\) :从前i个物品里选, 总体积不超过j的选法集合
属性: 最大值

状态计算

选择第i个物品:\(dp[i - 1][j - v[i]] + w[i]\)
不选第i个物品:\(dp[i - 1][j]\)
二者取最大值。

优化

滚动数组优化为一维:
\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])\)
\(dp[j] = max(dp[j], dp[j - v[i]] + w[i])\)
\(j\)从大到小枚举

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int w[N];
int v[N];
int dp[N];

int main()
{
    int n, W;
    
    cin >> n >> W;
    
    for (int i = 1; i <= n; i ++ ){
        cin >> v[i] >> w[i];
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = W; j >= v[i]; j -- )
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);  

    cout << dp[W] << endl;
    
    return 0;
}

例题:

完全背包

基本内容

特点

每件物品数量无限.

状态表示

\(dp[i][j]\)：从前i种物品中选择, 总体积不超过j的选法集合
属性：最大值

状态计算

对于第i种物品:
一件都不选:\(dp[i - 1][j]\)
选择一件: \(dp[i - 1][j - v[i]] + w[i]\)
选择两件: \(dp[i - 1][j - 2 \times v[i]] + 2 \times w[i]\)
...
选择k件:\(dp[i - 1][j - k \times v[i]] + k \times w[i]\)
取最大值

优化

时间优化：

1. 情况一 ：
   \(f[i - 1][j]\)
2. 情况二 : \(max(f[i][j - v] + w, f[i - 1][j - 2 * v] + 2 * w ... f[i - 1][j - k * v] + k * w ...\)
   已知:
   \(f[i][j - v] = max( f[i - 1][j - 2 * v] + w ... f[i - 1][j - k * v] + (k - 1) * w ... )\)
   \(f[i][j - v] + w\)
   \(max(f[i][j - v] + w, f[i - 1][j])\)

空间优化：
\(f[i - 1][j] , f[i][j - v] + w --> f[i][j]\)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 1e3 + 10;

int w[N];
int v[N];
int dp[N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
        
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            dp[j] = max(dp[j - v[i]] + w[i], dp[j]);
        
        
        
    cout << dp[m] << endl;
    
    return 0;
    
}

例题

多重背包

基本内容

特点

每个物品都有多个, 数量有限

状态表示

\(dp[i][j]\):从前i种物品中选, 总体不超过j的选法集合
属性:最大值

状态计算

类似于完全背包:
一件都不选:\(dp[i - 1][j]\)
选择一件: \(dp[i - 1][j - v[i]] + w[i]\)
选择两件: \(dp[i - 1][j - 2 \times v[i]] + 2 \times w[i]\)
...
选择\(s[i]\)件:\(dp[i - 1][j - s[i] \times v[i]] + s[i] \times w[i]\)
取最大值

优化

由于\(s[i]\)限制, 无法应用完全背包的方法进行优化
多重背包的优化方式:

1. 二进制优化为01背包
2. 单调队列优化

一、二进制优化
对于任意一个十进制数字总可以分割成若干个二进制之和,对于每一个\(s[i]\), 进行二进制拆分,拆分后的若干个背包转化为选与不选的01背包
二、单调队列优化

无优化:

/*

f[i][j] : 选前i中物品, 总体积不超过j时, 所有可能性的一个集合
属性: 最大值

1. 不选第i种物品: f[i - 1][j]
2. 选第i种物品: f[i][j - v] + w, f[i][j - 2 * v] + w * 2 , ..., f[i][j - s * v] + w * s


*/

#include <iostream>
#include <cstring>

using namespace std;


const int N = 110;

int dp[N][N];

int s[N], w[N], v[N];


int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i] >> s[i];
    
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ){
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            for (int k = 1; k * v[i] <= j && k <= s[i]; k ++ )
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);
        }
        
    cout << dp[n][m] << endl;
    
    
    return 0;
}

二进制优化:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2010;

int dp[N];
int w[N], v[N], cnt;

int n, m;

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ){
        int vx, wx, s;
        cin >> vx >> wx >> s;
        int k = 1;
        while (k <= s){
            cnt ++;
            v[cnt] = k * vx;
            w[cnt] = k * wx;
            s = s - k;
            k <<= 1;
        }
        if (s > 0){
            cnt ++;
            v[cnt] = s * vx;
            w[cnt] = s * wx;
        }
        
    }
    
    //for (int i = 1; i <= cnt; i ++ )
      //  cout << w[i] << ‘ ‘ << v[i] << endl;
    
    for (int i = 1; i <= cnt; i ++ )
        for (int j = m; j >= v[i]; j -- )
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    cout << dp[m] << endl;
    
    return 0;
        
}

例题

分组背包

基本内容

特点

有若干组物品, 每一组物品只能选择其中一种

状态表示

\(dp[i][j]\):从前i类物品里选择, 总体积不超过j的选法集合
属性:最大值

状态计算

对于第i类物品:
不选:\(dp[i - 1][j]\)
选择第一件: \(dp[i - 1][j - v[i][1]] + w[i][1]\)
选择第二件: \(dp[i - 1][j - v[i][2]] + w[i][2]\)
...
选择第k件: \(dp[i - 1][j - v[i][k]] + w[i][k]\)
取最大值

优化

一维优化：
\(dp[i - 1][j - v[i][k]] + w[i][k] --> dp[j - v[i][k]] + w[i][k]\)
逆向枚举

#include <iostream>

using namespace std;

const int N = 110;


int w[N][N];
int v[N][N];
int dp[N];
int s[N];
int n, m;

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 1; k <= s[i]; k ++ )
                if (j >= v[i][k])
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]); 
        
    cout << dp[m] << endl;
    
    
    return 0;
}

背包问题(待填)

原文：https://www.cnblogs.com/lhqwd/p/14630155.html