배낭 문제

배낭의 용량과 각 물건의 {무게, 가치}가 주어졌을 때 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제

구현

만약 물건을 쪼개어 담을 수 있다면, Greedy하게 풀 수 있지만, 그렇지 않은 경우 DP로 풀어야 한다! Greedy로 풀면 항상 최적의 답을 만족할 수 없고, Brute-force로 풀 경우 시간 초과가 발생하기 때문이다!

물거의 개수가 N이고, 각 물건의 {무게(w), 가치(v)} 가 주어졌을 때,

1. 물건 i(0≤i≤N)가 배낭의 용량을 초과하는 경우

   당연히 배낭에 들어갈 수 없다. 따라서 물건 i-1까지만 담는다!

2. 물건 i(0≤i≤N)가 배낭의 용량을 초과하지 않는 경우

   물건 i가 배낭의 용량을 초과하지 않는 경우, 다음과 같이 나누어 생각해볼 수 있다.
   이 물건을 넣는 것이 이득인가? 넣지 않는 것이 이득인가?
   1) 이득이 늘어나는 경우 : DP[i-1][j] < DP[i-1][j-W[i]]+V[i] 넣으면 된다!
   2) 그렇지 않은 경우 : DP[i-1][j] > DP[i-1][j-W[i]]+V[i] 넣지 않으면 된다!

   * DP[i-1][j-W[i]]+V[i]
   : i 번째 아이템이 들어갈 용량 확보 후, i번째 아이템을 넣고, 그 가치를 더해주는 것이다.

DP[i][j] : i개의 물건을 허용하고, 배낭의 용량이 j인 경우 배낭에 담을 수 있는 물건의 최대 가치

백준 12865번: 평범한 배낭 문제가 바로 0/1 Knapsack Problem 이다!

#include<iostream>
#define MAX_N 101
#define MAX_K 100001
using namespace std;

int N, K;
int W[MAX_N], V[MAX_N];
int DP[MAX_N][MAX_K];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> W[i] >> V[i];  // 물건들의 무게(w)와 가치(v)
    for(int i=1; i<=N; i++){
        for(int j=1; j<=K; j++){ // 배낭의 임시 용량
            if(j<W[i]) DP[i][j] = DP[i-1][j]; // 물건 i의 무게가 배낭의 임시 용량을 초과한 경우 물건 i-1까지만 담음
            else DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i]]+V[i]);
        }
    }
    cout << DP[N][K];
}