個数制限なしナップザック問題
個数制限なしナップザック問題(プログラミングコンテストチャレンジブック p58)
重さと価値がそれぞれであるような個の品物がある。
これらの中から重さの総和がを超えないように選んだ時の価値の総和の最大値を求める。
ただし、同じ品物をいくつでも選んでよい。
制約
アルゴリズム
番目までの品物から重さの総和がj以下となるように選んだ時の、価値総和の最大値
※
とすると、なのでkのループは最悪回まわる。従って、計算量は。
ここで、の計算において個選ぶ場合は、の計算で個選んだ場合と同様。
→の漸化式のの部分は既にの計算時に行っている。
従って、
と変形でき、で解ける。
コード
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]; } }