Knapsack

알고리즘에서 DP를 배울 때 유명한 문제. 0/1 배낭 채우기 알고리즘

 

백준 1535 안녕

 

 

풀이

 

DP	0	1	2	...	21	22	...	79	80
{1}	0	20	20	20	20	20	20	20	20
{1, 21}	0	20	20	20	30 (Max(dp[21], dp[0]+W[21])	50 (Max(dp[22], dp[1]+W[21])	50	50	50
{1, 21, 79}	0	20	20	20	30	50	50	50	50

1만 들어왔을 때 고려, 21 들어왔을 때 고려, 79 들어왔을 때 고려하는 방식을 통해 dp배열을 업데이트한다. 

새롭게 고려하는 항목이 21이라고 했을 때 W[21]이 플러스 되는 부분이다

뒤에서부터 업데이트를 해야 제대로 해결

 

import java.util.Arrays;
import java.util.Scanner;

public class Main_1535 {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int energy[] = new int[n];
		int happiness[] = new int[n];
		for(int i=0; i<n; i++) {
			energy[i] = s.nextInt();
		}
		for(int i=0; i<n; i++) {
			happiness[i] = s.nextInt();
		}
		int[] dp = new int[100];
		int max = 0;
		for(int i=0; i<n; i++) {
			for(int j=99; j>=0; j--) {
				int index = energy[i]+j;
				if(index<100) {
					dp[index] = Math.max(happiness[i]+dp[j], dp[index]);
				}
			}
		}
		for(int i=0; i<100; i++) {
			if(max<dp[i])
				max = dp[i];
		}
		System.out.println(max);
	}
}

3
1 21 79
20 30 25
50