🙇‍♀️냅색 알고리즘

최고 17kg의 무게를 저장할 수 있는 가방이 있다.

그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.

이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요?

각 종류별 보석의 개수는 무한이 많다.

한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

▣ 입력설명
첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.  

두 번째 줄부터 각 보석의 무게와 가치가 주어진다.  

가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.  

▣ 출력설명
첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.  

▣ 입력예제 1 
4 11
5 12
3 8
6 14
4 8

▣ 출력예제 1
28

🚀풀이

냅색 알고리즘을 이용하는 문제이다.

dp 공식은 다음과 같다.
dp[j] = max(dp[j], dp[j - jew.weight] + jew.value);
j 무게 만큼 담는 경우 dp[j - jew.weight]와 jew.value의 합을 왜 적는지 잘 이해해야한다.

dp가 계속 갱신되는것을 생각하면서 코드를 보자.

문제 이해를 잘 하기 위해서 보석 구조체를 만들고 값을 입력했다.

struct jewel
{
	int weight;
	int value;
};

int n, k, res= 0;
vector<jewel> v;
vector<int> dp;
void setting()
{
	cin >> n >> k;
	dp = vector<int>(k + 1);
	int a, b;
	for (int i = 0; i < n; ++i)
	{
		cin >> a >> b;
		v.push_back({ a, b });
	}
}

dp에는 빈 배열로 들어간 상태.
v에는 보석 정보가 들어가 있다.

dp를 계속 갱신시키는데 아래와 같이 한다.

void solve()
{
	for (int i = 0; i < n; ++i)
	{
		jewel jew = v[i];
		for (int j = jew.weight; j <= k; ++j)
		{
			dp[j] = max(dp[j], dp[j - jew.weight] + jew.value);
		}
		
	}

	for (int i = 0; i <= k; ++i)
	{
		res = max(res, dp[i]);
	}
	cout << res;
}

냅색을 이해한거같다..!

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

struct jewel
{
	int weight;
	int value;
};

int n, k, res= 0;
vector<jewel> v;
vector<int> dp;
void setting()
{
	cin >> n >> k;
	dp = vector<int>(k + 1);
	int a, b;
	for (int i = 0; i < n; ++i)
	{
		cin >> a >> b;
		v.push_back({ a, b });
	}
}

void solve()
{
	for (int i = 0; i < n; ++i)
	{
		jewel jew = v[i];
		for (int j = jew.weight; j <= k; ++j)
		{
			dp[j] = max(dp[j], dp[j - jew.weight] + jew.value);
		}
		
	}

	for (int i = 0; i <= k; ++i)
	{
		res = max(res, dp[i]);
	}
	cout << res;
}

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

	setting();
	solve();

	return 0;
}

참고