백준 12865 평범한 배낭

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

아이디어

• 대표적인 knapsack 문제
• 가치와, 종류로 dp를 나눠서 계산
• dp[N][K] : K의 무게에서, N개의 종류를 가지고있을때 최대의 가치
  • dp[N][K] = max(dp[N-1][K] : 안담는경우, dp[K-stuff[N]][N-1] : 담는경우)
  • 초기값 : dp[0][all] = 0
    • dp[1][stuff[1] ~ 끝 = stuff[1]

시간복잡도 계산

• 모든 종류에 대해 : N
• 모든 가치의 값을 구할 때 : K
• O(N*K)

자료구조

• dp 배열 : dp[N][K]
  • 가질수 있는 최대가치 : 1e5 * 1e3 = 1e8 > INT 가능
  • 이떄, dp 배열을 재활용해서 dp[K]으로만 사용할 수 도 있음
    • 이전값 덮어쓰는 경우
    • 단 이떄, 중복해서 물건 넣을 수 있는 경우는 상관없지만,
    • 한개씩밖에 넣지 못할 경우 뒤에서부터 값을 갱신해줘야함
• stuff pair<int, int>[]
  • 무게 최대값 : 1e5 > INT 가능
  • 가치 최대값 : 1e3 > INT 가능

코드(C++)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream>   using namespace std; typedef pair<int, int> pi2;   int dp[110][100010]; pi2 stuff[110]; int main() {          fill(&dp[0][0], &dp[109][100010], 0);     int N,K; cin >> N >> K;          for(int i=1; i<=N; i++) {         int a,b; cin >> a >> b;         stuff[i] = make_pair(a,b);     }          // 초기값 : dp[1][stuff[1] ~ 끝] = stuff[1]     for(int i=stuff[1].first; i<=K; i++) {         dp[1][i] = stuff[1].second;     }          for(int j=2; j<=N; j++) {         for(int i=0; i<=K; i++) {             // 안담는경우             dp[j][i] = dp[j-1][i];             // 무게를 담을 수 있으면             if(i-stuff[j].first >=0) dp[j][i] = max(dp[j][i], dp[j-1][i-stuff[j].first] + stuff[j].second);                      }     }          cout << dp[N][K] << '\n';          return 0; }   Colored by Color Scripter

cs

1차원 배열 사용해서 푸는경우 코드(C++)

#include <iostream>
 
using namespace std;
typedef pair<int, int> pi2;
 
int dp[100010];
pi2 stuff[110];
int main() {
    
    fill(dp, dp+100010, 0);
    int N,K; cin >> N >> K;
    
    for(int i=1; i<=N; i++) {
        int a,b; cin >> a >> b;
        stuff[i] = make_pair(a,b);
    }
    
    // 초기값 : dp[1][stuff[1] ~ 끝] = stuff[1]
    for(int i=stuff[1].first; i<=K; i++) {
        dp[i] = stuff[1].second;
    }
    
    for(int j=2; j<=N; j++) {
        // 이미 담은 물건을 다시 담을수있기 때문에 뒤에서부터 dp만들어줌
        for(int i=K; i>=0; i--) {
            // 무게를 담을 수 있으면
            if(i-stuff[j].first >=0) dp[i] = max(dp[i], dp[i-stuff[j].first] + stuff[j].second);
            
        }
    }
    
    cout << dp[K] << '\n';
    
    return 0;
}
 

문제유형

• DP - 이전 종류값 만을 포함
  • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
    • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
    • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
  • 대표문제 : knapsack
    • https://www.acmicpc.net/problem/12865
    • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
    • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치

비슷한 문제

• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/2294
• https://www.acmicpc.net/problem/2225
• https://www.acmicpc.net/problem/12865