多重背包

每一个物品数量是确定的

思路

1. 如果每个物品数量一件，那么就还是一个01背包问题
2. 可以把假设可以把第i件物品数量为num[i]，可以看成num[i]个相同的物品，这样还是一个01背包问题，但是时间和空间都接受不了

二进制优化

一个数总能写成二进制序列，可以分解成 把一个多个数量的物品分成这样几份，可以想要几个都可以实现，但是时间和空间变成了
看以看一下这个

// val[i] 物品i的价值
// weight[i] 物品i的重量
// a 单个物品的价值
// b 单个物品的重量
int k = 1;
cnt = 0;
while(k <= s)//k为枚举个数，s为物品总件数
{
	val[++cnt] = k * a;
	weight[cnt] = k * b;
	s -= k;   //总物品数减去合成数
	k *= 2;   //k倍增
}
if(s)//如果s有剩余，将剩余件数合成为新个体
{
	val[++cnt] = s * a;
	weight[cnt] = s * b;
}

例题 洛谷P1833 樱花

代码

#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
using lli = long long;
using ull = unsigned long long;
inline int read()
{
    int x = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            flag = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * flag;
}
// 01背包，完全背包，多重背包
// 只要价值能更大就行
// 根据数量可以做不同的判断
/*
    01背包：这个东西到底放不放
    不放：dp[j] = dp[j]
    放：dp[j] = dp[j - weight[i]] + val[i]
    dp[j] = std::max(dp[j], dp[j - weight[i]] + val[i]) // 倒序枚举避免重复
*/
/*
    完全背包:这个东西到底放不放
    不放：dp[j] = dp[j];
    放：放几个 dp[j] = std::max(dp[j], dp[j - weight[i]] + val[i]) // 正序枚举才会重复
*/
/*
    多重背包：这个东西放不放，放的话放几个（可以用二进制进行优化）
*/

int num[10004];
int val[10004];
int weight[10004];
int dp[1004];
signed main()
{
    int h1 = 0, m1 = 0, h2 = 0, m2 = 0;
    char c;
    scanf("%d %c %d %d %c %d", &h1, &c, &m1, &h2, &c, &m2);
    int tim = h2 * 60 + m2 - h1 * 60 - m1; // 背包总容量
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        std::cin >> weight[i] >> val[i] >> num[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (num[i] == 0) // 多重背包
        {
            for (int j = weight[i]; j <= tim; j++)
            {
                dp[j] = std::max(dp[j], dp[j - weight[i]] + val[i]);
            }
        }
        else if (num[i] == 1) // 01背包
        {
            for (int j = tim; j >= weight[i]; j--)
            {
                dp[j] = std::max(dp[j], dp[j - weight[i]] + val[i]);
            }
        }
        else // 多重背包
        {
            int cnt = 0;
            int tmp[num[i]] = {0};
            int tmp2[num[i]] = {0};
            int s = 1, k = num[i];
            while (s <= k)
            {
                tmp[++cnt] = s * val[i];
                tmp2[cnt] = s * weight[i];
                k -= s;
                s *= 2;
            }
            if (k)
            {
                tmp[++cnt] = k * val[i];
                tmp2[cnt] = k * weight[i];
            }
            for (int p = 1; p <= cnt; p++)
            {
                for (int j = tim; j >= tmp2[p]; j--)
                {
                    dp[j] = std::max(dp[j], dp[j - tmp2[p]] + tmp[p]);
                }
            }
        }
    }
    std::cout << dp[tim] << endl;
    return 0;
}