6. 多重背包问题 III

6.多重背包问题III

题目描述：

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

数据范围：

$0\lt N \le 10^3;0\lt V \le 2\times 10^4;0\lt v_i, w_i, s_i \le 2\times 10^4$

题解：

按照 $m \% v_i$ 的余数分组，每个分组都使用一个单调减队列，维护最大值。

AcWing 6. 多重背包问题 III【单调队列优化+图示】 - AcWing

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 2e4 + 10;
int t, n, m, k;
struct Node
{
    int v, w, s;
};
Node a[maxn];
int dp[maxn][maxm];
int q[maxm];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(n, m);
    for (int i = 1, v, w, s; i <= n; ++i)
    {
        read(a[i].v, a[i].w, a[i].s);
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i)
    {
        // 枚举余数
        for (int r = 0; r < a[i].v; ++r)
        {
            int hh = 0, tt = -1;
            // 单调减队列
            for (int j = r; j <= m; j += a[i].v)
            {
                // 如果队列长度大于了 s，弹出队首
                while (hh <= tt && j - q[hh] > a[i].s * a[i].v)
                    hh++;
                // 如果当前的值比队尾的大，弹出队尾
                // 同时也需要计算加多少倍的 w，因为 dp[i-1][j] 加过了。
                while (hh <= tt && dp[i - 1][q[tt]] + (j - q[tt]) / a[i].v * a[i].w <= dp[i - 1][j])
                    --tt;
                q[++tt] = j;
                // 计算需要加多少倍的 w
                dp[i][j] = dp[i - 1][q[hh]] + (j - q[hh]) / a[i].v * a[i].w;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}