ナップザック問題(分枝限定法)

目的

ナップザック問題とは、
「$n$個の荷物がありそれぞれ($i=1,2,...,n$)に価値$v_i$と重さ$w_i$が設定されています。
遠足には合計の重さが$W$以下の荷物しか持っていけません。
持っていく荷物の価値の総和の最大値を求めてください」
という問題です。ここで示すコードは分枝限定法と呼ばれる手法によってナップザック問題を解くコードです。

計算量

$O(n2^n)$

使い方

int n
荷物の数
long solve()
ナップザック問題の計算結果(持っていける荷物の価値の総和の最大値)をreturn。
long W
遠足に持っていける荷物の最大重量
long[][] a
a[i][0]とa[i][1]にそれぞれ荷物$i$の価値$v_i$と重さ$w_i$を代入してください。

ソースコード

import java.util.Arrays;
import java.util.Comparator;

class Main {
    long ans = 0;
    int N;
    long W;
    long[][] a;
    // a[i][0] = sc.nextLong(); // value
    // a[i][1] = sc.nextLong(); // weight

    void dfs(int curPos, long curWeight, long curValue) {
	ans = Math.max(ans, curValue);
	if (curPos >= N)
	    return;
	{
	    long resWeight = W - curWeight;
	    double relaxAns = curValue;
	    for (int i = N - 1; i >= curPos && resWeight != 0; --i) {
		if (resWeight >= a[i][1]) {
		    relaxAns += a[i][0];
		    resWeight -= a[i][1];
		    ans = Math.max(ans, (long) relaxAns);
		} else  {
		    relaxAns += 1.d * a[i][0] * (1.d * resWeight / a[i][1]);
		    resWeight = 0;
		}
	    }
	    if (relaxAns <= ans) {
		return;
	    }
	}
	dfs(curPos + 1, curWeight, curValue);
	if (curWeight + a[curPos][1] <= W) {
	    dfs(curPos + 1, curWeight + a[curPos][1], curValue + a[curPos][0]);
	}
    }

    double solve() {
	Arrays.sort(a, new Comparator<long[]>() {
		@Override
		    public int compare(long[] arg0, long[] arg1) {
		    return Double.compare((double) arg0[0] / arg0[1], (double) arg1[0] / arg1[1]);
		}
	    });
	dfs(0, 0, 0);
	return ans;
    }

}

Verified

yukicoder No.626 Randomized 01 Knapsack