2.11 背包学习

1020. 潜水员

#include <iostream>
#include <cstring>
using namespace std;

const int N = 22, M = 80;

int f[N][M];
int n, m, k;

int main() {
    cin >> n >> m >> k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    while (k --) {
        int a, b, c;
        cin >> a >> b >> c;
        for (int i = n; i >= 0; i --)
            for (int j = m; j >= 0; j --)
                f[i][j] = min(f[i][j], f[max(0, i - a)][max(0,j - b)] + c);
    }

    cout << f[n][m] << endl;
    return 0;
}

278. 数字组合

思路

就是01背包求方案数问题。
集合f[i,j]表示的是在前i个物品中，选择总体积恰好等于j的集合
集合划分为包括第i个物品和不包括第个物品
方案数就为这两种集合价值之和：
f[i, j] = f[i - 1, j] + f[i - 1, j - vi];

#include <iostream>
using namespace std;

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

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

1019. 庆功会

思路

本题数据范围较小，直接用\(n^3\)的暴力写法即可，板子题

#include <iostream>

using namespace std;

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

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

1023. 买书

思路

完全背包求方案数问题，和01背包求方案数问题类似
思路也差不多，套个完全背包的板子就行

#include <iostream>

using namespace std;

const int N = 1010;
int f[N];
int a[5] = {0, 10, 20, 50, 100};
int n;

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