まず、この記事を書く際の悲惨な経験について話します。最初は Gridea を使用しており、編集もそのエディタを使っていましたが、ある執筆中に、コンピュータが突然ブルースクリーンになりました。再起動後、md ファイルが開けなくなり、バイナリを確認すると全て 0 でした emmm（執筆中に保存したのに！！）。それ以来、hexo に切り替えました emmm。
記号の定義#
まず、いくつかの記号を定義します。アイテムの数を $n$ とし、
第 $i$ 個のアイテムの体積を $v_i$ 、価値を $w_i$ 、最大個数を $s_i$ とします。
バックパックの体積を $V$ 、動的計画法の配列を $dp$ とします。
振り返り#
まず、多重背包の最適化を振り返ります。（ $x$ はバックパックの体積が $j$ のとき、バックパックが耐えられる最大個数、すなわち $j /v$ です）
このとき、第 $i$ 個のアイテムの体積を $v$ とします。
dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (x - 1) v] + (x - 1)w, dp[i - 1, j - xv] + xw)
次に、完全バックパックの場合、$dp [i,j]$ と $dp [i,j - v]$ の関係を考えます。
dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (x - 1) v] + (x - 2)w, dp[i - 1, j - xv] + (x - 1)w)
（ある学生は、最後のバックパックが耐えられる数量がなぜ $x$ であるかと尋ねるかもしれませんが、実際にはそれは $x$ ではなく、$ j-v-(\frac {j-v}{v}) v$ で計算された状態は最終的に $xv$ を減少させます）
そして、私たちは驚くべきことに、 $max ()$ の最初の項以降の部分が $dp [i,j - v]$ と非常に似ており、$w$ のみが異なることに気付きました。したがって、$w$ を外に移動し、次のように置き換えることができます。
dp[i, j]= max(dp[i - 1, j], dp[i][j - v] + w)
否定#
次に、多重背包を見てみましょう。私たちはまだ柿を推測してみましょう（ここで $j$ が $sv$ よりもはるかに大きいと仮定します）
完全バックパックの方法を使って最適化できるかどうかを試みます。
dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (s - 1) v] + (s - 1)w, dp[i - 1, j - sv] + sw
dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (s - 1) v] + (s - 2)w, dp[i - 1, j - sv] + (s - 1)w)
どうやら、正しいように見えますね？（
しかし、項数を考慮すると、$dp [i, j-v]$ の項数と $dp [i,j]$ の項数は同じで、どちらも $s$ 項であり、$max ()$ の最初の項以降の項数とは異なるため、以前の方法で最適化することはできません。
新たな展開#
（この小節からは 1 次元配列を使用します。表現が簡単になるため、1 次元配列を学んでいない人は学んでください）
私たちはまだ $dp [j]$ を考慮し、柿を列挙します。
dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw
この柿を観察すると、状態 $j$ を更新する状態と $j$ は $v$ の意味で同余であるという性質を簡単に導き出すことができます。したがって、状態 $1$ から $V$ を $v$ クラスに分割し、それぞれは $v$ で余りが $0$ のもの、余りが $1$ のもの、$\cdots$、余りが $v-2$ のもの、余りが $v-1$ のものです。
元の dp[1]~dp[V] をこの $v$ クラスに変換できます（ここは考えるのが難しいですが、必ず理解してください）。
dp[0] dp[v] dp[2v] dp[3v] ... dp[kv]
dp[1] dp[1+v] dp[1+2v] dp[1+3v] ... dp[1+kv]
dp[2] dp[2+v] dp[2+2v] dp[2+3v] ... dp[2+kv]
...
dp[v-1] dp[v-1+v] dp[v-1+2v] dp[v-1+3v] ... dp[v-1+kv]
そして、これらの $v$ クラスをそれぞれ更新することができます。（ここで $... + kv$ は最後の状態を満たすためのものです。コードを参照してください）
このようなコードを書きます（最初は 2 次元で書きます）（1 次元に変更する場合は状態を逆順に列挙するか、ロール配列を利用する必要があります）。
for(int i = 1;i <= n;i++)
{
for(u = 0;u < v[i];u++)
{
for(int k = 0;u + k * v[i] <= V;k++)
{
int e = u + k * v[i];
for(int t = min(k - s * v[i], u)/*負の数にならないように*/;t < k;t += v[i])
{
dp[i][e] = max(dp[i - 1][e], dp[i - 1][t] + (e - t) / v[i] * w[i]);
}
}
}
}
そう、あなたは間違って見ていません。これは 4 重ループです。もしかしたら、このループがどうしてどんどん増えているのかと疑問に思うかもしれませんが、私たちはその時間計算量を分析しましょう。最初のループは $O (n)$ で、2 番目のループは各クラスの起点を列挙し、3 番目はそのクラス内の各状態を列挙します。2 番目と 3 番目の合計時間計算量は $O (V)$ です。最後のループは現在の状態に遷移できる状態を列挙するため、$O (s)$ です。したがって、全体の時間計算量は $O (nVs)$ です。
もし上記が理解できなければ、例を挙げてみましょう。
例を挙げましょう。仮に $2$ 件のアイテムがあり、$v_1 = 5$、$w_1 = 6$、$s_1 = 3$、$v_2 = 4$、$w_2 = 8$、$s_2 = 5$、バックパックの体積は $31$ です。
$i = 1$ のとき、すなわち最初のアイテムを列挙する際の dp 状態の分類は次のようになります。
dp[0] dp[5] dp[10] dp[15] dp[20] dp[25] dp[30]
dp[1] dp[6] dp[11] dp[16] dp[21] dp[26] dp[31]
dp[2] dp[7] dp[12] dp[17] dp[22] dp[27]
dp[3] dp[8] dp[13] dp[18] dp[23] dp[28]
dp[4] dp[9] dp[14] dp[19] dp[24] dp[29]
//第一（余数が0）のクラス
dp[1][0] = dp[0][0]
dp[1][5] = max(dp[0][5], dp[0][0] + w[1])
dp[1][10] = max(dp[0][10], dp[0][5] + w[1], dp[0][0] + 2 * w[1])
dp[1][15] = max(dp[0][15], dp[0][10] + w[1], dp[0][5] + 2 * w[1], dp[0][0] + 3 * w[1])
dp[1][20] = max(dp[0][20], dp[0][15] + w[1], dp[0][10] + 2 * w[1], dp[0][5] + 3 * w[1])
//最大で3個選べるので、最大体積（第二次元）は最大で3個のv[i]を減らすことができます
dp[1][25] = max(dp[0][25], dp[0][20] + w[1], dp[0][15] + 2 * w[1], dp[0][10] + 3 * w[1])
dp[1][30] = max(dp[0][30], dp[0][25] + w[1], dp[0][20] + 2 * w[1], dp[0][15] + 3 * w[1])
//以下同様
$i = 2$ も同様です。
単調キューの最適化#
もしかしたら、これだけ話しておいて単調キューの影すら見えないと疑問に思うかもしれませんが、実際には私たちが以前に行ったことはすべてそれのための準備でした。さあ、これがやってきました。
まず、最適化するのは上記のコードの第 4 層です：現在の状態の前の $s$ 個（隣接していない、各 2 つの間に $v$ の差がある）状態を使って現在の状態を更新します。
私たちは感覚的にこの図を考えてみましょう！（qwq
この図を見てみると、 $j$ は現在の状態を示し、$j'$ は次の状態、すなわち $j + v$ を示しています。灰色のセルは、現在の状態（ここでは $j$ または $j'$）を更新できる状態を示しています。
！！！！！注意：画像の最初の行の最左側は $j-sv$ であるべきですが、手が滑って間違えました（修正するのが面倒なので emmm）
私たちは観察することができます。状態が $v$ 増加するたびに、式 dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw は、最後（図の最左側）の更新可能な状態を失い、同時に最前（図の最右側）の更新可能な状態を得ます。
私たちの考えを整理しましょう。両端に挿入でき（$j$ が毎回 $v$ 増加するため、max 関数は毎回現在の状態 $j$ を更新するために使用できる状態が 1 つ増えます）、データを削除でき（これも 1 つ少なくなります）、最大値を求めるために（max 関数の要求により）$O (1)$ の時間計算量をサポートするデータ構造は何でしょうか？単調キューです！（単調キューにはインデックスが格納され、具体的なデータは格納されません）
一部の小さな詳細#
オフセット#
dp[0] dp[v] dp[2v] dp[3v] ... dp[kv]
dp[1] dp[1+v] dp[1+2v] dp[1+3v] ... dp[1+kv]
dp[2] dp[2+v] dp[2+2v] dp[2+3v] ... dp[2+kv]
...
dp[v-1] dp[v-1+v] dp[v-1+2v] dp[v-1+3v] ... dp[v-1+kv]
私たちはクラスの起点（dp[0]からdp[v-1]まで）を任意に選び、$u$ として見てみましょう。
dp[u] = dp[u]
dp[u+v] = max(dp[u] + w, dp[u + v])
dp[u+2v] = max(dp[u] + 2w, dp[u + v] + w, dp[u + 2v])
dp[u+3v] = max(dp[u] + 3w, dp[u + v] + 2w, dp[u + 2v] + w, dp[u + 3v])
...
max 関数内で、dp [] の後に加える値が異なることがわかります。これは非常に厄介です。単調キューで値を更新するのが非常に不便になるため、少し工夫をします。
dp[u] = dp[u]
dp[u+v] = max(dp[u], dp[u + v] - w) + w
dp[u+2v] = max(dp[u], dp[u + v] - w, dp[u + 2v] - 2w) + 2w
dp[u+3v] = max(dp[u], dp[u + v] - w, dp[u + 2v] - 2w, dp[u + 3v] -3w) + 3w
...
こうすることで、非常に快適になります。単調キューに入る値は常に dp[u + kv] - k*w です。現在の状態を更新する際には、最後に $a\times w$ を加えることを忘れないでください。$a$ は $（現在の状態 - 隊首状態）/v$ です。なぜなら、私たちは次のことを理解する必要があります。
私たちは、隊首 dp[u + kv] - k*w が $u$ 固定で、$k$ は範囲内で任意の最大値を取ることができることを知っています。現在の状態（仮に $u + bv$ とします）を更新する際、max 関数外のオフセットは正の $bv$ です。一方、dp[u + kv] は dp[u + kv] - k*w よりも $kw$ を少なく減少させており、最終的に max 関数外で再び $bv$ を加える必要があるため、総合的に見て $(b - k) * w$、すなわち $（現在の状態 - 隊首状態）/v * w$ を加えることになります。
キュー内の個数は $s+1$ 個で、$0$ から $s$ 個の前の状態を持つことになります。
ローリングアレイ#
前述のように、多重背包は逆順に列挙するか、データをバックアップする必要がありますが、単調キューの特性から、逆順に列挙するのはあまり便利ではないため、バックアップ配列の方法を採用します。
コード#
それでは、楽しくコードを書き始めましょう。
#include<iostream>
#include<cstdlib>
#include<cstring>//memcpy関数に必要なヘッダファイル
using namespace std;
const int N = 200005;
int q[N];//単調キュー、実際にはインデックスを格納
int g[N];//バックアップ配列
int dp[N];
int main()
{
int n, V;
cin >> n >> V;
for(int i = 1;i <= n;i++)
{
int v, w, s;//読み込みながら計算することで、配列を作成せずに済む
memcpy(g, dp, sizeof dp);//バックアップ
cin >> v >> w >> s;
for(int u = 0;u < v;u++)//各クラスの起点を列挙
{
int hh = 0, tt = -1;//単調キューは閉区間を維持するため、ttが1に等しいと
//要素が1つあることを示しますqwq
for(int k = u;k <= V;k += v)//ここでのkの意味は上記とは異なります
{
while(hh <= tt && (k - q[hh]) > s * v) hh++; //sを超えたらポップ
while(hh <= tt && g[q[tt]] - (q[tt] - u) / v * w < (g[k] - (k - u) / v * w)) tt--;//キューを単調に保つ
q[++tt] = k;//現在の状態を追加
if(hh <= tt) dp[k] = max(dp[k], g[q[hh]] + (k - q[hh]) / v * w);//現在の状態を更新
}
}
}
cout << dp[V];
return 0;
}
完結、花を撒きます！