多重背包

控制每件物品的数量

解法1：暴力拆分为01背包

#include<iostream>

using namespace std;

const int N = 10010;
int a[N], b[N], dp[N];

int main() {
    int n, m;
    int v, w, s;
    int t = 0;
    scanf("%d%d", &n, &m);
    while (n--) {
        scanf("%d%d%d", &v, &w, &s);
        while (s--) {
            a[++t] = v;
            b[t] = w;
        }
    }
    for (int i = 1; i <= t; i++)
        for (int j = m; j >= a[i]; j--)
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
    printf("%d\n",dp[m]);
    return 0;
}

#include "iostream"

using namespace std;

const int N = 1010;

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

int main() {
    int n, volume;
    scanf("%d%d", &n, &volume);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &v[i], &w[i], &s[i]);
        for (int j = volume; j >= v[i]; j--)
            for (int k = 1; k <= s[i]&&k*v[i]<=j; k++)
                dp[j] = max(dp[j], dp[j - v[i] * k] + k * w[i]);
    }
    printf("%d\n", dp[volume]);
    return 0;
}

解法2：二进制优化

#include<iostream>

using namespace std;

const int N = 20010;
int dp[N], a[N], b[N];

int main() {
    int n, v, idx = 0;
    scanf("%d%d", &n, &v);
    while (n--) {
        int vi, wi, si, k = 1;//vi-重量 wi-价值 si-单种物品数量 k-二进制左移位数
        scanf("%d%d%d", &vi, &wi, &si);
        while (si >= k) {
            a[++idx] = k * vi;
            b[idx] = k * wi;
            si -= k;
            k <<= 1;
        }
        if (si > 0) {
            a[++idx] = si * vi;
            b[idx] = si * wi;
        }
    }

    n = idx;
    for (int i = 1; i <= n; i++)
        for (int j = v; j >= a[i]; j--)
            //dp过程中会自动搜寻到复合的二进制数量排列
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
    printf("%d\n",dp[v]);
}

“任意一个实数可以由二进制数来表示”的画图举例

解法3：单调队列优化(还没有学会)