[알고리즘] 백준 12865 평범한 배낭

이희수·2024년 6월 1일

C++DP 백준 12865 알고리즘

알고리즘

목록 보기

12/25

문제

12865 평범한 배낭

구상

여러가지 경우의 수 중에서 최댓값을 구하면 되는 전형적인 DP 문제이다. 바로 코드를 살펴보자.

코드

#include<bits/stdc++.h> 
using namespace std;
int n,k,w,v;
int dp[100004];
int main() {
	cin>>n>>k;
	for(int i=0; i<n; i++){
		cin>>w>>v;
		for(int j=k; j>=w; j--){
			dp[j]= max(dp[j],dp[j-w]+v);
		}
	}
	cout<<dp[k];
	return 0;
}

1. 해당 물건을 넣기 전 가방의 최대 가치 + 해당 물건의 가치 (물건을 가방에 넣었을때)
2. 해당 물건을 넣었을때와 동일한 무게의 가방의 최대가치 (물건을 가방에 넣지 않았을때)

위 2가지 경우의 수를 비교해서 만약에 해당 물건을 가방에 넣는 경우가 더 가치가 높다면, 넣는 경우를 최적해로 저장한다.

그런데 위 코드를 살펴보면 j=k, 즉 최댓값부터 시작해서 탐색을 해간다.
for(int j=w; j<=k; j++) 방향으로 탐색하면 안되는 것일까?

두 방식의 차이점을 살펴보기 위해서 위 문제와 비슷한 문제인 백준 2294 동전 2 문제를 살펴보자.

백준 2294 동전 2

코드

#include<bits/stdc++.h>
using namespace std; 
int n, k,a[10001], temp, INF = 987654321;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n >> k; 
    fill(a, a + 10001, INF);
    a[0] = 0; 
    
    for(int i = 0; i < n; i++){
        cin >> temp; 
        for(int j = temp; j <= k; j++){
            a[j] = min(a[j], a[j - temp] + 1);
        }
    }
    if(a[k] == INF) cout << -1 << "\n"; 
    else cout << a[k] << "\n"; 
    return 0;
}

12865 평범한 배낭 문제와 비슷한 로직으로, 최적해를 기반으로 저장하며 탐색한다.
하지만 위 문제는 탐색방향이 오른쪽 (양의 방향) 임을 알 수 있다. 두 문제간에 어떠한 차이점이 있는걸까?

두 문제를 자세히 살펴보면, 동전 2 문제는 사용할 수 있는 자원의 양이 무한(동전을 몇개라도 사용 가능)인 반면, 평범한 배낭 문제는 일회성 자원(물품 하나)이다.

만약 평범한 배낭 문제에서 오른쪽 방향으로 탐색하는 경우를 생각해보자.

#include<bits/stdc++.h> 
using namespace std;
int n,k,w,v;
int dp[100004];
int main() {
	cin>>n>>k;
	for(int i=0; i<n; i++){
		cin>>w>>v;
		for(int j=w; j<=k; j++){
			dp[j]= max(dp[j],dp[j-w]+v);
		}
	}
	cout<<dp[k];
	return 0;
}
입력:
1 4
2 2

출력:
4
답:
2