[Algorithm] 🎒白駿12865普通リュック

0、問題

この問題は普通のリュックサックについての問題です.
一ヶ月後に国から召喚されたジュンヒは旅行に行く.悲しい世との隔絶、最大限楽しむ旅なので、持ち歩くリュックもできるだけ安くなります.
旅行が必要だと思っているものがN点ある.どれも重量Wと価値Vがあり、リュックサックに入れると準本でVを楽しむことができます.まだ行軍したことのない俊書は最大Kのリュックサックしか持っていない.できるだけ楽しく旅行するために、リュックサックに入れられるものの価値の最低価格を教えてあげます.
入力
第1行は、物品の数N(1≦N≦100)および準書に耐えられる重量K(1≦K≦100000)を与える.2行目から、N行を経て、各物品の重量W(1≦W≦100000)およびその物品の価値V(0≦V≦1000)が与えられる.
入力した数字はすべて整数です.
しゅつりょく
リュックサックに入れられるアイテムの価値の最高値を1行印刷します.

1.アイデア

dpを2 Dアレイに設定した後、最大収容重量に基づいて条件を区分する

2.コア解答

dp 2 Dアレイ、最大収容重量に依存

if(w[i] > j)
	dp[i][j] = dp[i-1][j];
else
	dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);

3.コード

import java.io.*;

public class DP_8 {
	static int w[],v[], dp[][], n, k;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s[] = br.readLine().split(" ");
		n = Integer.parseInt(s[0]);
		k = Integer.parseInt(s[1]);
		
		w = new int[n+1];
		v = new int[n+1];
		dp = new int[n+1][k+1];
		
		for(int i=1; i<=n; i++) {
			s = br.readLine().split(" ");
			w[i] = Integer.parseInt(s[0]);
			v[i] = Integer.parseInt(s[1]);
		}
		
		System.out.println(knapsack());
	}
	
	static int knapsack() {
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<k+1; j++) {
				if(w[i] > j)
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			}
		}
		
		return dp[n][k];
	}

}

4.結果

成功～