Limited Knapsack Algorithm
コードについての説明
各品物に個数の制約がついたナップサック問題のアルゴリズム. 少し意外だが, 個数制約なしの場合と同じ計算量で解くことができる.
本実装ではスライド最小値の考えを用いた実装をしている.
また各品物の個数を例えば $10$ コ → $1$ コ + $2$ コ + $4$ コ + $3$ コ のように $10$ 個以下の個数をすべて実現できるように
$2$ べきの重みを持つような品物に分解して 01 ナップザック問題に落とす方法もある. 計算量は $\O (nW \log M)$ ($M$ は品物の個数の最大値).
蟻本に詳しくのっているので参照してほしい.
時間計算量: $\O (nW)$ ($W$ は総重量の上限値)
コード
template<typename T>
//価値v,重さw,個数m,重さの上限W
T knapsack(vector<T>& v,vector<int>& w,vector<int>& m, int W){
int n = (int)v.size();
vector<T> dp(W+1), deqv(W+1);
vector<int> deq(W+1);
for(int i = 0; i < n; i++){
for(int a = 0; a < w[i]; a++){
int s = 0,t = 0;
for(int j = 0; j*w[i]+a <= W; j++){
T val = dp[j*w[i]+a] - j*v[i];
while(s < t && deqv[t-1] <= val){
t--;
}
deq[t] = j;
deqv[t++] = val;
dp[j*w[i]+a] = deqv[s] + j*v[i];
if(deq[s] == j-m[i]){
s++;
}
}
}
}
return dp[W];
}