読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

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

個数制限なしナップザック問題

Online Judge Algorithm

個数制限なしナップザック問題(プログラミングコンテストチャレンジブック p58)

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

アルゴリズム

 KNP_{i,j}:=i-1番目までの品物から重さの総和がj以下となるように選んだ時の、価値総和の最大値
{ \begin{array}{ll} KNP_{0,j}=0 && (i=0, 0\leq j \leq W) \\ KNP_{i,j} = \max \left \{ \left. KNP_{i-1,j-kw_{i-1}}+kv_{i-1} \right | 0 \leq k \right \} && (0 < i \leq n, 0\leq j \leq W) \end{array} }
{ \left \{ \left. KNP_{i,j} \right| j < 0 \right \} = \phi }
とすると、 1\leq v_iなのでkのループは最悪 W回まわる。従って、計算量は O(nW^2 )

ここで、 KNP_{i,j}の計算において k\geq 1個選ぶ場合は、 KNP_{i,j-w_{i-1}} の計算で k-1個選んだ場合と同様。
 KNP_{i,j}の漸化式の k\geq 1の部分は既に KNP_{i,j-w_{i-1} }の計算時に行っている。
従って、
{ \begin{array}{rl} KNP_{i,j}  & = \max \left \{ \left. KNP_{i-1,j-kw_{i-1}}+kv_{i-1} \right| 0\leq k \right \} \\ & = \max \left \{ KNP_{i-1,j} , \max \left \{ \left. KNP_{i-1,j-kw_{i-1}}+kv_{i-1} \right| 1\leq k \right \} \right \} \\  &= \max \left \{ KNP_{i-1,j} , \max \left \{ \left. KNP_{i-1,(j-w_{i-1})-kw_{i-1}}+kv_{i-1} \right | 0\leq k \right \} + v_{i-1} \right \} \\  &=  \max \left \{ KNP_{i-1,j}, KNP_{i,j-w_{i-1}}+v_{i-1} \right \} \end{array} }
と変形でき、 O(nW)で解ける。

コード

import java.util.*;
public class non_piece_concept_knapsack_problem {
	static Scanner stdin;
	static int[] w,v;
	static int n,W;
	static int[][] KNP;
	static int MAX_W = 10000;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new non_piece_concept_knapsack_problem();
	}
	non_piece_concept_knapsack_problem(){
		n = stdin.nextInt();
		w = new int[n];
		v = new int[n];
		KNP = new int[2][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() );
	}
	/*
	 * KNP[i][j]=i-1番目までの品物から重さの総和がj以下となるように選んだ時の、価値総和の最大値 O(nW)
	 */
	int solve1(){
		Arrays.fill(KNP[0], 0);
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j <= W; ++j){
				int pre = (i-1)&1, cur = i&1;
				if( j < w[i-1] ) KNP[cur][j] = KNP[pre][j];
				else KNP[cur][j] = Math.max(KNP[pre][j], KNP[cur][j-w[i-1]] + v[i-1] );
			}
		}
		return KNP[n&1][W];
	}
}