🙇‍♀️[Gold V] 평범한 배낭 - 12865

문제 링크

성능 요약

메모리: 41476 KB, 시간: 32 ms

분류

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

제출 일자

2023년 12월 18일 19:24:08

문제 설명

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

🚀풀이

냅색 문제에 도전했다…

일단 가장 간단하게 가치/무게가 높은 순으로 더해서 구하면 되지 않을까? 생각해서 구했다.
당연히 틀렸다.
조금더 좋은 경우의 수가 존재할 수 있다는건 쉽게 생각할 수 있다.

그래서 할 수 있는 모든 경우의 수를 탐색하여 풀려고했다.

완전 탐색도 좋은 방법이라고 생각했는데 너무 경우가 많아서 할 수 없는 방법이였다.
물품의 수가 100개까지 가능하므로 대충 생각하면 100!까지 경우가 나오니 불가능하다.

솔직히 이거 혼자 생각해서 푸는 사람 미친사람이다.

웬만하면 혼자 풀고싶은데 딱 느꼈다.
이거 혼자 못품.
그래서 인터넷 보고옴 ㅎ..
아무튼 코드는 봤으니 쩔수없고, 내것으로 만들려면 코드를 완벽히 이해하고 다음에 풀 수 있도록 해보자!

int n, k;
int cache[101][100001];
int w[101];
int v[101];

void solve()
{
	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
	{
		cin >> w[i] >> v[i];
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			if (j - w[i] >= 0)
				cache[i][j] = max(cache[i - 1][j], cache[i - 1][j - w[i]] + v[i]);
			else
				cache[i][j] = cache[i - 1][j];
		}
	}

	cout << cache[n][k];
}

모든 냅색 문제가 그런지는 모르겠지만 이 문제에서는 점화식이 있었다.
max(cache[i - 1][j], cache[i - 1][j - w[i]])
점화식이 왜 이런지 생각을 해보자.
여기서 i는 배낭에 넣을 물건 번호, j는 현재 배낭의 무게를 의미한다.

문제의 조건

4 7
6 13
4 8
3 6
5 12

조건을 대입한 결과 값

n 의 값 : 4     k 의 값 : 7

w[1] 의 값 : 6  v[1] 의 값 : 13
w[2] 의 값 : 4  v[2] 의 값 : 8
w[3] 의 값 : 3  v[3] 의 값 : 6
w[4] 의 값 : 5  v[4] 의 값 : 12
-------------------------------------------------------------
cache[1][1] 의 값 : 0
cache[1][2] 의 값 : 0
cache[1][3] 의 값 : 0
cache[1][4] 의 값 : 0
cache[1][5] 의 값 : 0
cache[1][6] 의 값 : 13
cache[1][7] 의 값 : 13
cache[2][1] 의 값 : 0
cache[2][2] 의 값 : 0
cache[2][3] 의 값 : 0
cache[2][4] 의 값 : 8
cache[2][5] 의 값 : 8
cache[2][6] 의 값 : 13
cache[2][7] 의 값 : 13
cache[3][1] 의 값 : 0
cache[3][2] 의 값 : 0
cache[3][3] 의 값 : 6
cache[3][4] 의 값 : 8
cache[3][5] 의 값 : 8
cache[3][6] 의 값 : 13
cache[3][7] 의 값 : 14
cache[4][1] 의 값 : 0
cache[4][2] 의 값 : 0
cache[4][3] 의 값 : 6
cache[4][4] 의 값 : 8
cache[4][5] 의 값 : 12
cache[4][6] 의 값 : 13
cache[4][7] 의 값 : 14

위의 결과 값을 분석해보자.
점화식의 해석에 따라서 순서대로 설명하자면
cache[1][1] : 1 번쨰 물건, 현재 배낭이 1 이라면 물건을 담을 수 없으므로 0
~~
cache[1][6] : 1 번째 물건, 현재 배낭이 6이라면 물건을 담을 수 있으므로 13

</br>

cache[2][4] : 2 번째 물건, 현재 배낭이 4라면 2 번쨰 물건을 담으므로 8
~~
cache[2][6] : 현재 배낭이 6이면 1 번째 물건을 담는것이 가치가 높으므로 13

</br>

cache[3][7] : cache[2][7]과 cache[2][7 - (3번 물건의 무게)] + 3번의 가치 중 큰 값을 저장함.
cache[2][7] 은 13이다.
cache[2][4] 는 6이고 3번의 가치는 8이다.
합하여 14의 가치를 지닌다.
그래서 cache[3][7] 은 14의 값으로 갱신된다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, k;
int cache[101][100001];
int w[101];
int v[101];

void solve()
{
	cin >> n >> k;
	cout << "n 의 값 : " << n << "  k 의 값 : " << k << endl;

	for (int i = 1; i <= n; ++i)
	{
		cin >> w[i] >> v[i];
		cout << "w[" << i << "] 의 값 : " << w[i] << "  v[" << i << "] 의 값 : " << v[i] << endl;
	}

	cout << "-------------------------------------------------------------" << endl;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			if (j - w[i] >= 0)
				cache[i][j] = max(cache[i - 1][j], cache[i - 1][j - w[i]] + v[i]);
			else
				cache[i][j] = cache[i - 1][j];

			cout << "cache[" << i << "][" << j << "] 의 값 : ";
			cout << cache[i][j] << endl;
		}
	}

	cout << cache[n][k];
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고