Skip to content

Instantly share code, notes, and snippets.

@NachiaVivias

NachiaVivias/knapsack.cpp

Created July 1, 2025 14:57
Show Gist options
  • Save NachiaVivias/3c8e9f2695bd050c2b6ac2c17a576447 to your computer and use it in GitHub Desktop.
Save NachiaVivias/3c8e9f2695bd050c2b6ac2c17a576447 to your computer and use it in GitHub Desktop.
Download ZIP
競プロ的ナップサック問題11問
Raw
knapsack.cpp
// The main purpose of this implementation is
// to show rough code patterns of solutions.
// I cannot guarantee the actual correctness of this code.
// Error reporting is welcome.
// 本ソースコードは解法の構造を示すためのものであり、
// 実際に正しく計算できることはあまり確認していません。
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
using namespace std;
using i64 = long long;
// W : weight
// V : value
// M : multiplicity
// Z : capacity of the knapsack
struct Item {
i64 W, V, M;
};
struct ItemFor6 {
i64 T, V;
};
struct ItemFor7 {
i64 T, S, V, M;
};
i64 knapsack_1(i64 Z, vector<Item> items){
vector<i64> dp(Z+1, 0);
for(auto [w,v,m] : items) for(i64 mi=0; mi<m; mi++){
for(i64 i=Z; i>=w; i--) dp[i] = max(dp[i], dp[i-w] + v);
}
return dp[Z];
}
i64 knapsack_2(i64 Z, vector<Item> items){
vector<i64> dp(Z+1, 0);
for(auto [w,v,m] : items){
for(i64 i=w; i<=Z; i++) dp[i] = max(dp[i], dp[i-w] + v);
}
return dp[Z];
}
i64 knapsack_3(i64 Z, vector<Item> items){
vector<i64> dp(Z+1, 0);
for(auto [w,v,m] : items) if(w <= Z){
m = min(m, Z / w);
vector<i64> buf = dp;
for(i64 s=0; s*w<=Z; s+=m){
i64 l = s * w;
i64 r = min(Z+1, (s + m) * w);
for(i64 i=l; i<r-w; i++) dp[i+w] = max(dp[i+w], dp[i] + v);
for(i64 i=r-w-1; i>=l; i--) buf[i] = max(buf[i], buf[i+w] - v);
}
for(i64 i=w*m; i<=Z; i++) dp[i] = max(dp[i], buf[i-w*m] + v*m);
}
return dp[Z];
}
i64 knapsack_4(i64 Z, vector<Item> items){
i64 Y = 0;
for(auto [w,v,m] : items) Y += v * m;
vector<i64> dp(Y+1, Z+1);
dp[0] = 0;
for(auto [w,v,m] : items) for(i64 mi=0; mi<m; mi++){
for(i64 i=Y; i>=v; i--) dp[i] = min(dp[i], dp[i-v] + w);
}
i64 ans = 0;
for(i64 y=0; y<=Y; y++) if(dp[y] <= Z) ans = y;
return ans;
}
i64 knapsack_5(i64 Z, vector<Item> items){
vector<pair<i64,i64>> WV1, WV2;
WV1.push_back({0,0});
WV2.push_back({0,0});
for(auto [w,v,m] : items){
vector<pair<i64,i64>> tmp;
i64 n = WV1.size(), p = 0, q = 0, xv = -1;
while(q < n){
i64 pw = 0, pv = 0;
if(p < n && WV1[p].first <= WV1[q].first + w){
pw = WV1[p].first;
pv = WV1[p].second;
p++;
} else {
pw = WV1[q].first + w;
pv = WV1[q].second + v;
q++;
}
if(xv < pv){ xv = pv; tmp.push_back({ pw, pv }); }
}
swap(WV1, tmp);
swap(WV1, WV2);
}
i64 ans = 0;
for(auto [w,v] : WV1) if(w <= Z){
while(WV2.back().first + w > Z) WV2.pop_back();
ans = max(ans, v + WV2.back().second);
}
return ans;
}
i64 knapsack_6(i64 Z, i64 K, vector<ItemFor6> items){
i64 S = 0;
for(i64 z=Z; z>0; z/=K) S++;
vector<vector<i64>> V(S+1);
for(auto a : items) if(a.T < S) V[a.T].push_back(a.V);
i64 ans = 0;
for(i64 s=0; s<S; s++){
sort(V[s].begin(), V[s].end());
auto take = [&]() -> i64 {
i64 res = V[s].back(); V[s].pop_back();
return res;
};
while(Z%K > 0 && !V[s].empty()){ ans += take(); Z--; }
while(V[s].size()){
i64 v = 0;
for(i64 k=0; k<K && !V[s].empty(); k++) v += take();
V[s+1].push_back(v);
}
Z /= K;
}
return ans;
}
i64 knapsack_7(i64 Z, vector<ItemFor7> items){
i64 K = 2;
i64 maxT = 0;
for(auto a : items) maxT = max(maxT, a.T);
vector<vector<Item>> ranked(maxT+2);
for(auto a : items) ranked[a.T].push_back({a.S, a.V, a.M});
vector<i64> dp = {0};
for(i64 t=0; t<=maxT && Z > 0; t++){
for(auto [w,v,m] : ranked[t]){
i64 z = dp.size() - 1;
i64 xm = m;
if(m >= K-1) xm = K-1 + (m-(K-1)) % K;
for(i64 mi=0; mi<xm; mi++){
for(i64 i=0; i<w; i++) dp.push_back(dp.back());
for(i64 i=0; i<=z; i++) dp[i+w] = max(dp[i+w], dp[i] + v);
}
ranked[t+1].push_back({ w, v*K, (m-xm)/K });
}
vector<i64> nx;
for(i64 i=Z%K; i<i64(dp.size()); i+=K) nx.push_back(dp[i]);
nx.push_back(dp.back());
swap(dp, nx);
Z /= K;
}
return dp[min<i64>(Z,i64(dp.size()-1))];
}
i64 knapsack_8(i64 Z, vector<Item> items){
for(auto& a : items) if(items.back().V * a.W < a.V * items.back().W) swap(items.back(), a);
auto top = items.back(); items.pop_back();
vector<i64> V(top.W, 0);
for(auto [w,v,m] : items) V[w%top.W] = max(V[w%top.W], v - top.V * (w / top.W));
vector<i64> dp(top.W, 0);
for(i64 w=Z%top.W; w<top.W; w++) dp[w] -= top.V;
for(i64 w=0; w<top.W; w++) if(0 < V[w]){
i64 g = gcd(w, top.W);
i64 xg = top.W / g;
for(i64 s=0; s<g; s++){
i64 p = 0;
for(i64 i=0; i<xg*2; i++){
i64 q = p + w;
if(q < top.W){
dp[q] = max(dp[q], dp[p] + V[w]);
} else {
q -= top.W;
dp[q] = max(dp[q], dp[p] + V[w] - top.V);
}
}
}
}
i64 ans = 0;
for(i64 w=0; w<top.W; w++) ans = max(ans, dp[w]);
return ans + Z / top.W * top.V;
}
i64 knapsack_9(i64 Z, vector<Item> items){
auto MaxPlus = [](i64 w, vector<Item> items, vector<i64>& dp){
i64 z = dp.size() - 1;
vector<i64> A = {0};
i64 sz = z / w;
sort(items.begin(), items.end(),
[](const Item& l, const Item& r){ return l.V > r.V; });
for(auto& a : items){
for(i64 i=0; i<a.M && (i64)A.size()<=sz; i++){
A.push_back(A.back() + a.V);
}
}
for(i64 s=0; s<w; s++){
i64 n = (z-s)/w + 1;
vector<i64> Idx(n+1);
vector<i64> d0(n), d1(n);
for(i64 i=0; i<n; i++) d0[i] = dp[i*w+s];
d1[0] = d0[0] + A[0];
Idx.back() = n-1;
i64 bi = 1; while(bi < n) bi *= 2;
for(i64 q=bi/2; q>0; q/=2) for(i64 m=q; m<n; m+=q*2){
i64 l = m-q, r = min(m+q, n);
Idx[m] = Idx[l];
for(i64 t=Idx[l]; t<=Idx[r]; t++){
if(t<=m && m-t<i64(A.size()) && d1[m] < d0[t] + A[m-t]){
d1[m] = d0[t] + A[m-t];
Idx[m] = t;
}
}
};
for(i64 i=0; i<n; i++) dp[i*w+s] = d1[i];
}
};
vector<i64> dp(Z+1);
vector<vector<Item>> ranked(Z+1);
for(auto a : items) if(a.W <= Z) ranked[a.W].push_back(a);
for(i64 w=1; w<=Z; w++) if(ranked[w].size()){
MaxPlus(w, move(ranked[w]), dp);
}
return dp[Z];
}
i64 knapsack_10(i64 Z, vector<Item> items){
i64 INF = 2ll << 60;
i64 maxW = 0;
sort(items.begin(), items.end(),
[](Item l, Item r){ return l.V * r.W < l.W * r.V; });
for(auto [w,v,m] : items) maxW = max(maxW, w);
vector<vector<Item>> A(maxW+1), B(maxW+1);
i64 off = 0;
while(items.size()){
auto& a = items.back();
i64 n = min(Z / a.W, a.M);
off += n * a.V; Z -= n * a.W; a.M -= n;
A[a.W].push_back({ a.W, a.V, n });
if(a.M) break;
items.pop_back();
}
for(auto a : items) B[a.W].push_back(a);
auto MaxPlus = [](i64 w, vector<Item> items, vector<i64>& dp){
i64 z = dp.size() - 1;
vector<i64> A = {0};
i64 sz = z / w;
sort(items.begin(), items.end(),
[](const Item& l, const Item& r){ return l.V > r.V; });
for(auto& a : items){
for(i64 i=0; i<a.M && (i64)A.size()<=sz; i++){
A.push_back(A.back() + a.V);
}
}
for(i64 s=0; s<w; s++){
i64 n = (z-s)/w + 1;
vector<i64> Idx(n+1);
vector<i64> d0(n), d1(n);
for(i64 i=0; i<n; i++) d0[i] = dp[i*w+s];
d1[0] = d0[0] + A[0];
Idx.back() = n-1;
i64 bi = 1; while(bi < n) bi *= 2;
for(i64 q=bi/2; q>0; q/=2) for(i64 m=q; m<n; m+=q*2){
i64 l = m-q, r = min(m+q, n);
Idx[m] = Idx[l];
for(i64 t=Idx[l]; t<=Idx[r]; t++){
if(t<=m && m-t<i64(A.size()) && d1[m] < d0[t] + A[m-t]){
d1[m] = d0[t] + A[m-t];
Idx[m] = t;
}
}
};
for(i64 i=0; i<n; i++) dp[i*w+s] = d1[i];
}
};
i64 Z2 = maxW * (maxW + 1);
vector<i64> dpal(Z2+1, -INF-1), dpbe(Z2+1, 0);
dpal[0] = 0;
for(i64 w=1; w<=maxW; w++) if(A[w].size()){
for(auto& a : A[w]) a.V = -a.V;
MaxPlus(w, move(A[w]), dpal);
}
for(i64 w=1; w<=maxW; w++) if(B[w].size()){
MaxPlus(w, move(B[w]), dpbe);
}
for(i64 i=Z2-1; i>=0; i--) dpal[i] = max(dpal[i], dpal[i+1]);
i64 ans = off;
for(i64 de=0; de<=maxW*(maxW-1); de++) if(dpal[de] >= -off){
ans = max(ans, off + dpal[de] + dpbe[de+Z]);
}
return ans;
}
i64 knapsack_11(i64 Z, vector<Item> items){
i64 INF = 2ll << 60;
i64 maxV = 0;
for(auto [w,v,m] : items) maxV = max(maxV, v);
sort(items.begin(), items.end(),
[](Item l, Item r){ return l.V * r.W < l.W * r.V; });
for(auto [w,v,m] : items) maxV = max(maxV, v);
vector<vector<Item>> A(maxV+1), B(maxV+1);
i64 off = 0;
while(items.size()){
auto& a = items.back();
i64 n = min(Z / a.W, a.M);
off += n * a.V; Z -= n * a.W; a.M -= n;
A[a.V].push_back({ a.W, a.V, n });
if(a.M) break;
items.pop_back();
}
for(auto a : items) B[a.V].push_back(a);
auto MaxPlus = [INF](i64 v, vector<Item> items, vector<i64>& dp){
i64 z = dp.size() - 1;
vector<i64> A = {0};
i64 sz = z / v;
sort(items.begin(), items.end(),
[](const Item& l, const Item& r){ return l.W > r.W; });
for(auto& a : items){
for(i64 i=0; i<a.M && (i64)A.size()<=sz; i++){
A.push_back(A.back() + a.W);
}
}
for(i64 s=0; s<v; s++){
i64 n = (z-s)/v + 1;
vector<i64> Idx(n+1);
vector<i64> d0(n), d1(n, -INF);
for(i64 i=0; i<n; i++) d0[i] = dp[i*v+s];
d1[0] = d0[0] + A[0];
Idx.back() = n-1;
i64 bi = 1; while(bi < n) bi *= 2;
for(i64 q=bi/2; q>0; q/=2) for(i64 m=q; m<n; m+=q*2){
i64 l = m-q, r = min(m+q, n);
Idx[m] = Idx[l];
for(i64 t=Idx[l]; t<=Idx[r]; t++){
if(t<=m && m-t<i64(A.size()) && d1[m] < d0[t] + A[m-t]){
d1[m] = d0[t] + A[m-t];
Idx[m] = t;
}
}
};
for(i64 i=0; i<n; i++) dp[i*v+s] = d1[i];
}
};
i64 Z2 = maxV * (maxV + 1);
vector<i64> dpal(Z2+1, 0), dpbe(Z2+1, -INF-1);
dpbe[0] = 0;
for(i64 v=1; v<=maxV; v++) if(A[v].size()){
MaxPlus(v, move(A[v]), dpal);
}
for(i64 v=1; v<=maxV; v++) if(B[v].size()){
for(auto& a : B[v]) a.W = -a.W;
MaxPlus(v, move(B[v]), dpbe);
}
for(i64 i=Z2-1; i>=0; i--) dpbe[i] = max(dpbe[i], dpbe[i+1]);
i64 ans = off;
i64 q = Z2;
for(i64 de=maxV*(maxV-1); de>=0; de--){
while(dpal[de] + Z < -dpbe[q]) q--;
ans = max(ans, off - de + q);
}
return ans;
}
int main(){
// nothing
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment