多重背包模板

多重背包：

有N种物品和一个容量为V的背包。第i种物品最多有numi件可用。
每件物品的重量是wi，价值是vi。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 105;
int n, m, need[maxn], value[maxn], num[maxn], dp[maxn];
//need是花费
//value是价值
//num是数量
int main() {
    //n是种类，m是总钱数
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &need[i], &value[i], &num[i]);

    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= need[i]; --j)
            for (int k = 1; k <= num[i] && k*need[i] <= j; ++k)
                dp[j] = max(dp[j], dp[j - k * need[i]] + k * value[i]);

    printf("%d\n", dp[m]);
    return 0;
}

参考博客 https://www.cnblogs.com/FrankChen831X/p/11423350.html

多重背包模板

推荐阅读