[백준] 12865-평범한 배낭(C++), 배낭 문제 알고리즘

문제링크: www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

제목 그대로 평범한 배낭문제 (knapsack) 입니다. 

 

배낭 문제는 

 

• 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)
• 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)

두가지로 분류됩니다.

 

 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로

그리디 알고리즘을 사용합니다.

 

물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법을 사용합니다.

 

해당문제는 dp를 사용하는 방식입니다.

 

전제조건

n은 물건개수, k는 가져갈 수 있는 무게값

w[]는 물건에 대한 무게값들

v[]는 해당 물건에 대한 가치값

 

 

i는 i번째 물건 j는 무게를 나타냅니다. 

즉, dp[i][j]는 i번째 물건까지 최대 j무게까지 가능할때 최고의 가치값입니다. 

 

점화식은

if(w[i]<=j) 일때는

dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j]

else

dp[i][j] = dp[i - 1][j]

이 됩니다.

 

이해가 가지 않으신다면 직접 표로 작성해보세요.

물건	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

정답코드입니다.

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


int n, k;
int w[100001] = { 0, };
int v[1001] = { 0, };
int dp[101][100001] = { 0, };

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	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 (w[i] <= j) {
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			}
			else
				dp[i][j] = dp[i - 1][j];
		}
	cout << dp[n][k] << endl;


	return 0;
}

 

심화문제는 7579번 앱!

좌측 검색누르셔서 제가 푼 코드 확인하실수 있습니다.