yukicoder : No.2686 商品券の使い道

こちらはすんなり。
https://yukicoder.me/problems/no/2686

問題

N個の商品があり、それぞれの価格と価値が与えられる。
初日はM円、2日目はQ円以下の範囲でいくつかの商品を購入可能とする(なお、各商品は1つしかない)。
購入できる商品の価値の総和の最大値を求めよ。

解法

まず初日分に関し購入パターンを全通り試し、その後高速ゼータ変換で「初日にある商品群のsubset内で得られる最大価値」を求めておこう。
次に2日目分の購入パターンを全通り試し、2日目に購入しない商品群について、先ほど求めた最大価値を足しこめばよい。

int N;
ll M,Q;
ll A[20],B[20];
ll sum[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,N) cin>>A[i]>>B[i];
	int mask;
	FOR(mask,1<<N) {
		ll a=0,b=0;
		FOR(i,N) if(mask&(1<<i)) {
			a+=A[i];
			b+=B[i];
		}
		if(a<=M) sum[mask]=b;
	}
	FOR(i,N) FOR(mask,1<<N) if(mask&(1<<i)) sum[mask]=max(sum[mask],sum[mask^(1<<i)]);
	ll ret=0;
	FOR(mask,1<<N) {
		ll a=0,b=0;
		FOR(i,N) if(mask&(1<<i)) {
			a+=A[i];
			b+=B[i];
		}
		if(a<=Q) {
			ret=max(ret,b+sum[((1<<N)-1)^mask]);
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

これは割と典型。