[JAVA] SWEA 3282- 0/1 Knapsack

Solution

• dp[i][j] 부피가 j이고 i 번째 물건까지 고려했을 때 최대 가치 합
• i번째 물건이 정해진 부피인 j보다 작거나 같다면? -> i번째 물건 넣는 것 고려할 수 있음
  • 그럼 물건을 넣는 것과 안 넣는 것 중 가치가 최대인 방법이 물건 i 번까지를 고려 & 부피가 j일 때 구할수 있는 최대 가치 합
    -> dp[i][j] = Math.max(dp[i - 1]j - w[i]] + cost[i],
    dp[i - 1][j]);
• i 번째 물건이 정해진 부피인 j보다 크다면? -> 고려조차 할 수 없음
  • 안 넣는 방법밖에 선택권이 없다면 이전에 구한 최댓값을 가져옴
    -> dp[i][j] = dp[i-1][j]

Code

import java.util.*;
class Solution
{
	public static void main(String args[]) throws Exception
	{
		 Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        int TC = sc.nextInt();
        for(int tc=1; tc<=TC; tc++) {
            sb.append("#").append(tc).append(" ");

            int N = sc.nextInt();
            int K = sc.nextInt();

            int w[] = new int[N+1];
            int cost[] = new int[N+1];

            for(int i=1; i<=N; i++){
                w[i] = sc.nextInt();
                cost[i] = sc.nextInt();
            }

            int dp[][] = new int[N+1][K+1];
            for(int i=1; i<=N; i++){
                for(int j=1; j<=K; j++){
                    if(w[i] > j){
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[i][j] = Math.max(dp[i - 1][j - w[i]] + cost[i],
                                dp[i - 1][j]);
                    }
                }
            }
            sb.append(dp[N][K]).append("\n");

        }
        System.out.println(sb);
    }
}