yukicoder : No.3401 Large Knapsack Problem

似たとき味のものを解いたことある気がする。
https://yukicoder.me/problems/no/3401

問題

いわゆる重さと価値に関する、個数制限なしの典型的なナップサック問題である。
なお、荷物の総和の上限は10^9と大きい。
また、荷物の種類Nは20以下であり、各荷物の価値・重さは10^3以下である。

解法

ナップサックのほとんどを重さあたりの価値が大きいもので埋め、残りの重さだけまじめにナップサック問題を解けばよい。
以下の例では、重さの総和が2^20になるまでDPでまじめに価値を最大化し、残りは１種類の荷物で埋めるケースを総当たりしている。

int N;
int W;
int A[20],B[20];
ll dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		FOR(j,(1<<20)-B[i]) chmax(dp[j+B[i]],dp[j]+A[i]);
	}
	ll ret=0;
	FOR(i,N) {
		FOR(j,min(W,1<<20)) chmax(ret,dp[j]+1LL*(W-j)/B[i]*A[i]);
	}
	cout<<ret<<endl;
}

まとめ

コードは短いね。