acwing算法提高之动态规划--背包模型（四）

1 基础知识

暂无。。。

2 模板

暂无。。。

3 工程化

题目1：货币系统。

解题思路：完全背包模型求方案数。

状态定义f[i][j]：从前i个物品中选体积恰好为j的方案数。
状态转移f[i][j]，以下情况的累加和，

1. 不选择第i个物品，即f[i-1][j]。
2. 选择第i个物品1次，即f[i-1][j-v[i]]。
3. 选择第i个物品2次，即f[i-1][j-2*v[i]]。
4. ……
5. 选择第i个物品max次，即f[i-1][j-max*v[i]]。

状态转移可以简化成，

状态转移f[i][j]，以下情况的累加和，

1. 不选择第i个物品，即f[i-1][j]。
2. 选择第i个物品1次~max次的累加和，为f[i][j-v[i]]。

初始化，f[0][0] = 1。

最终答案为f[n][m]。

同样的，也可以将状态降维，C++代码如下，

#include <iostream>

using namespace std;

const int M = 3010;
int n, m;
long long f[M];

int main() {
    cin >> n >> m;
    
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        for (int j = x; j <= m; ++j) {
            f[j] += f[j-x];
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

题目2：货币系统，求最简的面值表示。

解题思路：完全背包求方案数的应用。

C++代码如下，

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

using namespace std;

const int N = 110, M = 25010;
int n, m;
int v[N];
int f[M];

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> v[i];
        sort(v, v + n);
        
        int res = 0;
        m = v[n - 1];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            if (f[v[i]] == 0) res += 1;
            for (int j = v[i]; j <= m; ++j) {
                f[j] += f[j - v[i]];
            }
        }
        cout << res << endl;
    }
    
    return 0;
}

题目3：混合背包问题。

解题思路：完全背包归为一类，体积从小到大枚举；01背包和多重背包归为一类，体积从大到小枚举。

C++代码如下，

#include <iostream>

using namespace std;

const int M = 1010; 
int n, m;
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        
        if (s == 0) {
            //完全背包问题
            for (int j = v; j <= m; ++j) {
                f[j] = max(f[j], f[j - v] + w);
            }
        } else {
            if (s == -1) s = 1;
            for (int k = 1; k <= s; k <<= 1) {
                for (int j = m; j >= k * v; --j) {
                    f[j] = max(f[j], f[j - k * v] + k * w);
                }
                s -= k;
            }
            if (s) {
                for (int j = m; j >= s * v; --j) {
                    f[j] = max(f[j], f[j - s * v] + s * w);
                }
            }
        }
    }
    
    cout << f[m] << endl;
       
    return 0;
}