kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

01ナップザック問題

Online Judge Algorithm

01ナップザック問題(プログラミングコンテストチャレンジブック p34)

重さと価値がそれぞれ w_i , v_iであるような n個の品物がある。
これらの中から重さの総和が Wを超えないように選んだ時の価値の総和の最大値を求める。
制約
1\leq n \leq 100
1\leq w_i , v_i \leq 100
1\leq W \leq 10000

アルゴリズム1

i番目以降の品物から重さの総和がj以下となるように選んだ時の総和価値の最大値を返す関数rec(i,j)で再帰してDFSすると O(2^n )。
同じi,jについてrec(i,j)が何度も呼び出されて無駄→メモ化。
i,jの組は高々nW個、rec(i,j)内での再帰呼び出しは2回なので O(nW)で解ける。

コード1

C++のvectorみたいに、メモテーブルの初期化を

Arrays.fill(KNP[0],-1);
Arrays.fill(KNP, KNP[0]);

としてしまってはまった。
fill()はプリミティブ型の配列以外だと同じ参照が入るだけなので使えない。

import java.util.*;
public class knapsack_problem {
	static Scanner stdin;
	static int[] w,v;
	static int n,W;
	static int[][] KNP;
	static int MAX_N = 100, MAX_W = 10000;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new knapsack_problem();
	}
	knapsack_problem(){
		n = stdin.nextInt();
		w = new int[n];
		v = new int[n];
		KNP = new int[MAX_N+1][MAX_W+1];
		for(int i =0 ; i < n; ++i){
			w[i] = stdin.nextInt();
			v[i] = stdin.nextInt();
		}
		W = stdin.nextInt();
		System.out.println( solve1() );
	}
	//メモ化O(n,W)
	int solve1(){
		//初期化
		for(int i=0; i < KNP.length; ++i) Arrays.fill(KNP[i], -1);
		return rec(0,W);
	}
	//i番目以降の品物から重さの総和がj以下になるよう選んだ時の総和価値の最大値を返す
	int rec(int i, int j){
		if( KNP[i][j] >= 0 ) return KNP[i][j]; // メモ済み
		else if( i == n ) return 0; //もう選ぶものが無い
		else if( j < w[i] ) return rec( i+1, j ); //i番目の品物は積載量オーバー
		else return Math.max( rec(i+1, j), rec(i+1, j-w[i]) + v[i] ); //入れる場合と入れない場合
	}
}

アルゴリズム2

アルゴリズム1をボトムアップに見ていくと漸化式で
KNP_{i,j}:= i番目以降の品物から重さの総和がj以下になるよう選んだ時の総和価値の最大値
i=n, 0\leq j\leq Wについて、KNP_{n,j} = 0
0\leq i < n, 0\leq j \leq Wについて
KNP_{i,j} = \begin{cases} KNP_{i+1,j} && (j < w_{i}) \\ \max \{ KNP_{i+1,j}, KNP_{i+1,j-w_i} +v_{i} \} && (otherwise) \end{cases}
と書いてDPで解ける O(nW)。

コード2

int solve2(){
	Arrays.fill(KNP[n], 0);
	for(int i=n-1; i >= 0; --i){
		for(int j=0; j <= W; ++j)
			KNP[i][j] = j < w[i] ? 
					KNP[i+1][j] : Math.max(KNP[i+1][j], KNP[i+1][j-w[i]]+v[i]);
	}
	return KNP[0][W];
}

アルゴリズム3

ループの向きを逆に考える O(nW)。
KNP_{i,j}:= i-1番目までの品物から重さの総和がj以下になるよう選んだ時の総和価値の最大値
i=0, 0\leq j\leq Wについて、KNP_{0,j} = 0
0< i \leq n, 0\leq j \leq Wについて
{ KNP_{i,j} = \begin{cases} KNP_{i-1,j} && (j < w_{i-1}) \\ \max \{ KNP_{i-1,j}, KNP_{i-1,j-w_{i-1} }+v_{i-1} \} && (otherwise) \end{cases} }

コード3

int solve3(){
	Arrays.fill(KNP[0], 0);
	for(int i=1; i <= n; ++i){
		for(int j=0; j <= W; ++j)
			KNP[i][j] = j < w[i-1] ?
					KNP[i-1][j] : Math.max(KNP[i-1][j], KNP[i-1][j-w[i-1]]+v[i-1]);
	}
	return KNP[n][W];
}

アルゴリズム4

i番目までの品物から重さの総和がj以下となるように選んだ状態　から
i+1番目までの品物から重さの総和がj以下となるように選んだ状態　と
i+1番目までの品物から重さの総和がj+w[i]以下となるように選んだ状態に遷移できると考えたDP O(nW)。

コード4

初めに初項だけでなく、KNP[i][j]を価値の総和の最小値で初期化しないとダメ。
max は他の状態(i,j)からの遷移で更新したものとどちらが大きいか比べる

int solve4(){
	for(int i=0; i<=n; ++i) Arrays.fill(KNP[i], 0);
	for(int i=0; i<n; ++i){
		for(int j=0; j<=W; ++j){
			KNP[i+1][j] = Math.max(KNP[i+1][j], KNP[i][j]); //iを選ばないかどうか
			if( j+w[i] <= W) //積載可能な場合
				KNP[i+1][j+w[i]] = Math.max( KNP[i+1][j+w[i]], KNP[i][j]+v[i]); //iを選ぶかどうか
		}
	}
	return KNP[n][W];
}