[C++] 12865: 평범한 배낭

쩡우·2022년 11월 20일
0

BOJ algorithm

목록 보기
4/65

12865번: 평범한 배낭 (acmicpc.net)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

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

예제 입력 1

4 7
6 13
4 8
3 6
5 12

예제 출력 1

14

풀이

다이내~믹 프로그래밍 문제!
다이나믹 프로그래밍이란?! "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘" - 나무위키
전에 했던 연산 또 하면 넘 복잡하니까 그걸 저장해놨다가 다음 연산 때 사용하는 방식이다!

이런 식으로 {최대 무게 , 요소 무게 , 요소 가치}가 주어졌을 때 요소 가치 합의 최대를 구하는 문제를 knapsack problem, 배낭 문제라고 한다.

혼자 문제만 쳐다보고 있으니까 모르겠어서 풀이 방식을 찾아보았다. 2차원 배열로 하는 방식과 1차원 배열로 하는 방식이 있던데 내가 보기에는 1차원이 더 편리하고 직관적(인가?)으로 보여서 1차원 배열 방식 dp로 풀어봤다.

n개의 물품이 있고, 배낭 무게의 최대치는 max_weight라고 해보자.
일단 dp array를 (max_weight + 1)칸을 만든다.(각 칸의 index는 그 칸에 들어갈 수 있는 무게이다. 요소의 크기가 그 칸의 index보다 작거나 같으면 넣어볼 수 있다.)
그 후 n개의 모든 물품에 대해 dp array를 뒤에서부터 전부 확인한다.

확인 방식은 다음과 같다.
i (1 ~ n-1) 번째의 물품의 무게가 dp array의 index값보다 작으면, 2개의 값 중 큰 값을 넣는다.
1. 이전에 dp array에 들어있었던 값.
2. (dp array의 index - i번째 물품의 weight) + i번째 물품의 value.

각 dp 과정을 알기 위해 dp array의 값을 표로 만들어보았다. 백준 예제에서는 가방 최대 무게가 7이므로 array가 1부터 7까지 7칸이다. 입력 물품 개수가 4개이므로 array는 총 4번 바뀐다. 처음 array는 모두 0으로 초기화되어 있다.

처음 들어온 물건은 weight가 6, value가 13이다.
7에 들어갈 수 있네? array[7] == 0과 array[7 - 6] + 13 == 13을 비교해서 더 큰 값을 넣는다.
6에도 들어갈 수 있네? array[6] == 0과 array[6 - 6] + 13 == 13을 비교해서 더 큰 값을 넣는다.
5부터는 못 들어간다.

두 번째로 들어온 물건은 weight가 4, value가 8이다.
7에 당연히 들어갈 수 있다. array[7] == 13과 array[7 - 4] + 13 == 13을 비교해서 더 큰 값을 넣는다.
6도 마찬가지.
5에 들어갈 수 있다. array[5] == 0과 array[5 - 4] + 8 == 8를 비교해서 넣는다.
...

세 번째로 들어온 물건은 weight = 3, value = 6.
index 7에 들어갈 수 있다. 여기서 잘 보면
array[7] == 13이고 array[7 - 3] + 6 == 14이다.
여태 7에 들어갈 수 있던 최대값보다, 4까지 들어갈 수 있는 가치 최대값에 현재 물건의 가치를 더한 값이 더 크다. 그러면 7에 들어가는 최대값을 갱신하고, 비교를 계속하면 된다.

dp array의 각 값은 "(index값) 무게에 들어갈 수 있는 최대 가치"를 뜻한다.
(6, 13), (4, 8) ,(3, 6) ,(5, 12) 물건을 각각 받았으므로, 마지막 array를 보면
6번째 칸에는 13,
4번째 칸에는 8,
3번째 칸에는 6,
5번째 칸에는 12의 가치가 들어있는 것을 볼 수 있다. 7번째 칸에는 13이 아닌 4 + 3의 가치값인 8 + 6 == 14가 들어있는 것을 볼 수 있다.

따라서 max_weight == 7에 들어갈 수 있는 최대값인 14가 정답이 된다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100001] = {0, };
int weight[100];
int value[100];
int	n, max_weight;

void	input_data(void);
int		find_max_value(void);
void	print_arr(void);

int	main(void)
{
	input_data();
	int result = find_max_value();
	cout << result;

	return (0);
}

void input_data(void)
{
	cin >> n >> max_weight;
	
	int i = -1;
	while (++i < n)
	{
		int	w, v;
		cin >> w >> v;
		weight[i] = w;
		value[i] = v;
	}

	return ;
}

int	find_max_value(void)
{
	int	i = -1;
	while (++i < n)
	{
		int check_weight = max_weight + 1;
		while (--check_weight >= 1)
			if (check_weight >= weight[i])
				dp[check_weight] = max(dp[check_weight], dp[check_weight - weight[i]] + value[i]);
		//print_arr();
	}

	return (dp[max_weight]);
}

void print_arr(void)
{
	int i = 0;
	while (++i < max_weight + 1)
		cout << dp[i] << " ";
	cout << endl;

	return ;
}

야호!!!!!!😆😆😆😆

profile
Jeongwoo's develop story

0개의 댓글