Codeforces ECR #061 : E. Knapsack

なんだこりゃ。
https://codeforces.com/contest/1132/problem/E

問題

シンプルなナップサック問題である。
1～8の重さのアイテムの個数が与えられる。
アイテム群の部分集合のうち、重さの総和が最もWに近づく値はいくつか。

解法

1～8の最小公倍数は(2^3)*3*5*7=840である。
f(n,k) := 1～nまでの重さのアイテムの部分集合のうち、mod 840がkであるもののうち総和が最もWに近いもの
とし、f(n-1,k)からf(n,m)の遷移を総当たりしよう。

ll W;
ll C[9];
ll dp[9][840];
ll ret;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W;
	ll sum=0;
	
	FOR(i,840) FOR(j,9) dp[j][i]=-1LL<<60;
	dp[0][0]=0;
	
	for(i=1;i<=8;i++) {
		cin>>C[i];
		FOR(x,840) if(dp[i-1][x]>=0) {
			FOR(y,840) if(C[i]>=y && dp[i-1][x]+y*i<=W) {
				ll add=min((C[i]-y)/840,(W-(dp[i-1][x]+y*i))/(840*i));
				dp[i][(x+y*i)%840]=max(dp[i][(x+y*i)%840],dp[i-1][x]+y*i+add*(840*i));
			}
		}
	}
	
	ll ret=0;
	FOR(i,840) ret=max(ret,dp[8][i]);
	
	cout<<ret<<endl;
}

まとめ

余りに着目するナップサック問題はたまに出るね。