백준 12865번 <평범한 배낭>

백준 알고리즘 12865번

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

으아 이거 모각코 때 도전했는데 못 푼 문제...

---

12865번

배낭에 넣을 수 있는 물품의 수와 준서가 버틸 수 있는 무게가 주어지고 그다음 줄부터 각 물건의 무게와 그 물건의 가치가 주어진다.

배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구해서 출력한다.

---

문제 해결

이 문제는... knapsack problem이라고 하여 문제를 푸는 방법이 있다.

이 문제는 knapsack problem 중에서 물품을 쪼갤 수 없는 0-1 knapsack problem이다.

ㅎㅎ

덕분에 knapsack problem에 대해 공부하여 포스팅을 하였다.

 

https://seunghee114-blog.tistory.com/87

[알고리즘] 0-1 배낭 문제 / 0-1 Knapsack Problem

이 포스팅에 적혀있는

1.  i = 0 이거나 w = 0 인 경우에 배열의 값은 0이다.

(0번째 짐을 사용하면 당연히 가치는 0... 배낭 무게의 최댓값이 0이면 당연히 가치도 0..)

 

2. i번째 짐의 무게가 배낭 무게의 최댓값보다 크면 배열의 값은 bag[i-1][w]이다.

(i번째 짐이 너무 무거워서 배낭에 넣을 수 없어!!!)

 

3. i번째 짐의 무게가 배낭 무게의 최댓값보다 작거나 같으면

   배열의 값은 bag[i-1][w]와 bag[i-1][w-weight[i]] + value[i]이다.

   말로 풀어보자면

   i-1번째 짐까지만 사용하고 배낭 무게의 최댓값이 w인 경우의 값과

   i-1번째 짐까지만 사용하고 배낭 무게의 최댓값이 (w - i번째 짐의 무게)인 경우의 값 + value[i]

   두 개 중 더 큰 값을 배열의 값으로 한다.

(i번째 짐을 넣을 거니까 i번째 짐의 가치를 더하고 배낭 무게의 최댓값에서 i번째 짐의 무게를 빼는 것이다.)

 

이거를 코드로 구현하고 돌리면 된다!!

---

코드

import java.util.Scanner;

public class Main {

	static int n, k;
	static int bag[][], weight[], value[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		k = sc.nextInt();

		bag = new int[n + 1][k + 1];

		weight = new int[n + 1];
		value = new int[n + 1];

		for (int i = 1; i < n + 1; i++) {
			weight[i] = sc.nextInt();
			value[i] = sc.nextInt();
		}

		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < k + 1; j++) {
				if (i == 0 || j == 0) {
					bag[i][j] = 0;
				} else if (weight[i] > j) {
					bag[i][j] = bag[i - 1][j];
				} else {
					bag[i][j] = Math.max(bag[i - 1][j], value[i] + bag[i - 1][j - weight[i]]);
				}

			}
		}

		System.out.println(bag[n][k]);

	}
}

---