yukicoder : No.2167 Fibonacci Knapsack

こういう「実は探索が必要な範囲は狭い」という問題、割と苦手…。
https://yukicoder.me/problems/no/2167

問題

N個の荷物があり、それぞれの重さと価値が与えられる。
なお、価値の値はフィボナッチ数列を成す。

重さWの範囲で荷物を運ぶとき、価値の総和を最大化せよ。

解法

価値がフィボナッチ数列を成すことから、価値の高い順に荷物を見たときに、持てるのに荷物を2つ連続スキップする意味はない。
ということを踏まえ枝刈り探索していく。

int T;
int N;
ll TW,W[105],F[107];
ll ret;

void dfs(int cur,ll TW,ll V) {
	ret=max(ret,V);
	if(cur==0) return;
	if(W[cur]>TW) {
		dfs(cur-1,TW,V);
	}
	else {
		dfs(cur-1,TW-W[cur],V+F[cur]);
		//スキップしてもいいケース
		if(cur>=2&&TW<W[cur]+W[cur-1]&&TW>=W[cur-1]&&V+F[cur+1]-2>ret) {
			dfs(cur-1,TW,V);
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[1]=1;
	F[2]=2;
	for(i=3;i<=100;i++) F[i]=F[i-1]+F[i-2];
	
	cin>>T;
	while(T--) {
		cin>>N>>TW;
		for(i=1;i<=N;i++) cin>>W[i];
		ret=0;
		dfs(N,TW,0);
		cout<<ret<<endl;
	}
}

まとめ

コードは短いんだけど、こういうの考察苦手だ。