混合背包

admin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
const int N=10001;
int m, n;
int w[N], c[N], num[N], f[N];
void ZeroOnePack(int cost, int weight)// 01背包，只能取一次
{
    for (int v = m; v >= weight; v--)
        f[v] = max(f[v], f[v - weight] + cost);
}
void CompletePack(int cost, int weight) //完全背包
{
    for (int v = weight; v <= m; v++)//m 包的大小，v是包的遍历
        f[v] = max(f[v], f[v - weight] + cost);
}
void MultiplePack(int cost, int weight, int num)
{
    for (int j = m; j >= weight; j--)
        for (int k = 1; k <= num; k++)
            if (j - k * weight >= 0)
                f[j] = max(f[j], f[j - k * weight] + k * cost);
}
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> c[i] >> num[i];

    for (int i = 1; i <= n; i++) {
        if (num[i] == 1) //0-1背包
            ZeroOnePack(c[i], w[i]);
        else if (num[i] == 0) //完全背包
            CompletePack(c[i], w[i]);
        else //多重背包
            MultiplePack(c[i], w[i], num[i]);
    }
    cout << f[m] << endl;
    return 0;
}