[BOJ-Gold5] 12865번 평범한 배낭

💡 풀이

✔️ 배낭 알고리즘

• 배낭 알고리즘 참고
  
• dp[i][k] = 최대무게가 k인 가방에서 i번째 물건까지 판단했을때의 최대가치
• dp 점화식

  경우 1) i번째 물건의 무게가 배낭의 무게(k) 초과 -> i 담지 않음
     => dp[i][k] = dp[i-1][k]
     
   경우 2) 배낭의 무게를 초과하지 않음 -> 2가지 경우
    2-1) i번째 물건 담지 않음 => dp[i][k] = dp[i - 1][k]
    2-2) i번재 물건 담음 => dp[i][k] = i번째 물건의 가치 + dp[i - 1][k - i번째 물건의 무게]

• dp[i][k] = max(dp[i - 1][k], i가치 + dp[i - 1][k - i무게]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int[][] item = new int[n + 1][2];
		for(int i = 1; i<=n; i++){
			st = new StringTokenizer(br.readLine());
			item[i][0] = Integer.parseInt(st.nextToken()); // weight
			item[i][1] = Integer.parseInt(st.nextToken()); // value
		}

		int[][] dp = new int[n+1][k+1];
		for(int i = 1; i<=k; i++){ // 무게
			for(int j = 1; j<=n; j++){  // 가치
				dp[j][i] = dp[j-1][i];
				if (i - item[j][0] >= 0){
					dp[j][i] = Math.max(dp[j-1][i], item[j][1] + dp[j-1][i-item[j][0]]);
				}
			}
		}
		System.out.println(dp[n][k]);
	}

}