BOJ_12865_평범한 배낭

1.

구분: 다이나믹 프로그래밍, 배낭 문제

언어: Java

전략

• 0-1 knapsack문제를 이용하여 문제를 해결한다. 
• 물건을 차례대로 고려한다(포함하거나 포함하지 않거나) - 배낭 무게 내에서 물건을 포함할지 말지 고르고, 또한 그 가치를 포함/비포함 중 더 큰 것을 선택한다.
• 방법이 2가지가 있다 

1, 2차원 배열을 활용하여 문제를 해결

- d[i][j]: i번째 물건을 고려할 때, 가방의 무게가 j일때 최대 가치 

- i 번 물건을 고려(꼭 포함해야 하는게 아니다)

- i-1번에서 현재 물건 포함한 상황과, i-1번째에서 포함하지 않은 상황 중 더 큰 것을 선택한다.

 

2. 1차원 배열을 활용하여 문제를 해결

- d[j]: 가방 무게가 j일때 최대 가치

- 가방의 무게가 가장 최대일 때 부터 현재 가치와, 물건을 포함했을때의 가치 중 더 큰것을 선택

---

2. 코드

//2차원 배열을 이용하는 경우

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt(); //물건 수
		int w = scanner.nextInt(); //가방 무게
		
		int[] weights = new int[n+1]; //물건들의 무게를 담는다
		int[] profits = new int[n+1]; //물건들의 가치를 담는다
		
		for(int i = 1; i<n+1; i++) {
			weights[i] = scanner.nextInt();
			profits[i] = scanner.nextInt();
		}
		
		int[][] d = new int[n+1][w+1];
		
		for(int i = 1; i<n+1; i++) {
			for(int j = 1; j<=w; j++) {
				
				if(weights[i]<=j) { //해당 물건을 가방에 넣을 수 있다.
                //그냥 물건을 안넣거나, 물건을 넣거나
					d[i][j] = Math.max(d[i-1][j], profits[i]+d[i-1][j-weights[i]]);
				}else { //해당 물건을 가방에 넣을 수 없다
					d[i][j] = d[i-1][j];
				}
			}
		}
		
		System.out.println(d[n][w]);
	}

}

//1차원 배열을 이용하는 경우 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int W = scanner.nextInt();
		
		int[] weights = new int[n+1];
		int[] profits = new int[n+1];
		
		for(int i = 1; i<n+1; i++) {
			weights[i] = scanner.nextInt();
			profits[i] = scanner.nextInt();
		}
		
		int[] d = new int[W+1];
		
		for(int i = 1; i<n+1; i++) {
			//담을 수 있는 상황만 돈다(맨 뒤에서 부터 고려)
			for(int w = W; w>=weights[i]; w--) {
				//해당 물건을 가방에 넣을 수 있다.
				d[w] = Math.max(d[w] , profits[i]+d[w-weights[i]]);
				
			}
		}
		
		System.out.println(d[W]);
	}

}

---

3.

0-1 knapsack 그 자체

1차원 배열을 이용하면 메모리를 줄일 수 있다.