TopCoder SRM 821 : Div1 Medium KnapsackTweak

そっちの手もあったか。
https://community.topcoder.com/stat?c=problem_statement&pm=17365

問題

品物の価格一覧と、所持金Pが与えられる。
品物を複数選び、その価格の総和が所持金と一致するよういわゆるナップサック問題を解きたい。

ここで、各品物の価格を任意の整数に調整できるとする。
選んだ品物の価格の総和が所持金と一致するように調整する場合、各品物の価格の変更量の絶対値の最大値を最小化せよ。

解法

自分は二分探索で解いた。
解がD以下であるならば、各品物の価格Cを代わりに[C-D,C+D]の範囲の商品が選べる、と考えてDPした。
累積和を取りながら処理を行えば、良い。DPの過程では[0,P]ではなく、一時的に[-P,2P]の範囲にはみ出すことを許容すること。

別解としては、以下もある。まず、以下を求めよう。
f(x) := 選んだ品物の総和がxとなる選び方のうち、最多品物数
すると、各状態から価格をPに合わせることを考えると、ceil(abs(D-x)/f(x))の最小値が解となる。

int N,T;
int V[55];
int from[301010];
int to[301010];
class KnapsackTweak {
	public:
	int can(int d) {
		if(d<0) return 0;
		
		ZERO(from);
		int i,j;
		for(i=100000;i<=300000;i++) from[i]=1;
		FOR(i,N) {
			for(j=0;j<=300000;j++) {
				int ok=0;
				if(from[j]-(j>=1?from[j-1]:0)) ok=1;
				int L=max(0,j-V[i]-d);
				int R=min(300000,j-V[i]+d);
				if(L<=R&&from[R]-(L>=0?from[L-1]:0)) ok=1;
				to[j]=ok;
				if(j) to[j]+=to[j-1];
				if(j==T+100000&&ok) return 1;
			}
			swap(from,to);
		}
		return 0;
		
		
	}
	
	int smallest(vector <int> items, int target) {
		int ret=100000;
		int i;
		N=items.size();
		T=target;
		FOR(i,N) V[i]=items[i];
		for(i=20;i>=0;i--) if(can(ret-(1<<i))) ret-=1<<i;

		return ret;
	}
}

まとめ

後者の方が実装楽だったかもな…。