[C/C++ 백준 12865번] 평범한 배낭 (Gold 5)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

처음 봤을 때는 동전류의 문제인 줄 알았는데, 한번 넣은 물건을 다시 쓸 수 없어 까다로웠던 문제같다.

 

이 문제는 Knapsack problem이라고 잘 알려진 알고리즘이다. 

받은 물건들을 무게 오름차순으로 정렬해준뒤, dp 2차원 배열을 만들어 dp[i][j]가 i번째 물건까지 사용할 경우, j까지 무게를 담을 수 있을 때 최대 가치라고 하자.

 

이 때 i번째 물건을 쓸 수 있느냐 없느냐, 그리고 쓸 수 있을 경우 쓰느냐 마느냐 이렇게 결정해서 dp를 생성해주면 된다.

주의 해야 할 점은 물건을 아예 안쓰는 경우도 있다는거,, 그래서 밑의 코드 같은 경우는 물건을 i=1부터 받았다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct Tool{
	int W;
	int V;
}Tool;
Tool tool[101];
bool comp(Tool a, Tool b){
	return a.W < b.W;
}
int dp[101][100001]={};
int main(void){
	int N, K;
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++){
		scanf("%d %d",&tool[i].W, &tool[i].V);
	}
	sort(tool, tool + N, comp);
	for(int i=0; i<=N; i++){
		for(int j=0; j<=K; j++){
			if(j==0 || i==0)	
				dp[i][j]=0;
			else{
				if(tool[i].W <= j)
					dp[i][j] = max(tool[i].V+dp[i-1][j-tool[i].W],dp[i-1][j]);
				else
					dp[i][j] = dp[i-1][j];
			}	
		}
	}
	printf("%d", dp[N][K]);
}