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

해결 방법

분명 3학년때 배웠는데..

Knapsack Problem : Greedy vs DP

Greedy?

• 가장 비싼 것 부터 채우기
  그러나, 아이템이 값에 비해 무겁다면? : 최적해❌

• 가장 가벼운 것 부터 채우기
  그러나, 아이템이 가벼운 것에 비해 값이 떨어지면? : 최적해❌

• 무게 당 값을 계산, 높은 것 부터 총 용량을 넘지 않을 때까지 채우기

  > example
  * 아이템 1 : 50만원/5kg = 10만원/1kg
  * 아이템 2 : 60만원/10kg = 6만원/1kg
  * 아이템 3 : 140만원/20kg = 7만원/1kg

  1>3>2 순으로 담아야겠다.
  가방 용량이 30이라고 할 때 , 아이템1+아이템3 = 190만원이 최적일까?
  ❌아니다❌ 아이템2+아이템3 = 200만원이 최적해이다.

👉 이처럼 아이템을 쪼갤 수 없는 0-1 냅색 문제는 Greedy로 최적해를 구할 수 없다
👉 그러나 아이템을 조각낼 수 있는 냅색문제라면 Greedy로 최적해를 구할 수 있다 ✔

DP

dp[i][j] : 가방 용량이 j이고 1~i개의 아이템을 살펴봤을 때, 가치의 최댓값

만약 물건을 넣을 수 있다면? (가방의 용량 >= 아이템i의 무게)

• 아이템 i를 포함하지 않는 경우
  dp[i][j] = i-1개 아이템 중, 최적을 이루는 부분집합 👉 dp[i-1][j]
• 아이템 i를 포함하는 경우
  이익 = 가방용량 - 아이템i의 무게를 초과하지 않고, i-1개 아이템으로 얻는 최적 이익 + 아이템i의 값

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

소스 코드

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

const int n_ = 101;
const int k_ = 100001;
int dp[n_][k_]; 
/*
dp[i][j] : 가방 용량이 j이고, 1~i번째 물건까지 살펴봤을 때 가치의 최댓값 
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
> dp[i-1][j] : 용량 j인 가방에 i번째 물건을 넣지 않았을 때
> dp[i-1][j-w[i]] + v[i] : i번째 물건을 넣었을 때
	- 물건 넣을 만큼 공간을 확보 : j-w[i] 
*/
int W[n_]; 
int V[n_];

int N,K;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.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], dp[i-1][j-W[i]] + V[i]);
			else dp[i][j] = dp[i-1][j];
		}
	} 
	
	cout<<dp[N][K];
}

제출 결과

핫하 K 범위 잘못봤다