2.15 背包学习

1021. 货币系统

思路

完全背包求方案数，与01背包类似

#include <iostream>

using namespace std;

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

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

532. 货币系统

思路

这题首先要理解题目意思
理解后可以得知，答案就是从a数组中选出的，将a数组排序后，观察每个数是否能被前面的数表示
若能被表示说明不选，不能则选
就可以转化成一个完全背包求方案数问题

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

using namespace std;

const int N = 110, M = 25010;
int f[M];
int a[N];

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

7. 混合背包问题

思路

混合背包是由01背包，完全背包，多重背包组成的混合体，事实上这三种背包在集合的确定上是相通的
且当前物品的最大价值和上件物品是什么样的没有关系，故能直接计算
对于每种不同的物品，用各自的方法计算即可。
同时由于多重背包使用二进制优化方法时和01背包状态转移类似，可以合并

#include <iostream>

using namespace std;

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (!s) {
            for (int j = v; j <= m; j ++) {
                f[j] = max(f[j], f[j - v] + w);
            }
        }else {
            if (s == -1) s = 1;            //若当前为01背包，则只有一种
            //多重背包二进制优化模板
            for (int k = 1; k <= s; k *= 2) {
                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;
}

10. 有依赖的背包问题

思路

树形dp + 分组背包
将每个节点当做一个物品组。用dfs遍历到叶子结点，然后一层层向上的物品组中选择最优解

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

using namespace std;

int n, m;
const int N = 110;
int f[N][N];
int v[N], w[N];
int h[N], e[N], ne[N], idx;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int son = e[i];
        dfs(son);
        
        for (int j = m - v[u]; j >= 0; j --) {    //按体积划分
            for (int k = 0; k <= j; k ++) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    
    for (int i = m; i >= v[u]; i --) f[u][i] = f[u][i - v[u]] + w[u]; //添加该节点的价值
    for (int i = 0; i < v[u]; i ++) f[u][i] = 0;
    //本节点中，不可能存在比该节点体积小的还有价值的方案，因为有依赖，该节点必须选择
}

int main() {
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    int root;
    for (int i = 1; i <= n; i ++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) {
            root = i;
        }else add(p, i);
    }
    
    dfs(root);
    
    cout << f[root][m] << endl;
    return 0;
}