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

문제 :

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

분석 :

 

이 문제는 knapsack 알고리즘의 대표적인 문제이다.

🍙 knapsack 알고리즘

무게와 가치가 따로 있고 최대 가치를 구하는 문제

 

greedy론 최대 가치를 보장 할 수 없기 때문에 DP로 접근해야 한다.

 

D[i][j] - j 만큼의 무게를 가진 i번째까지 물건들의 가치

V[i] - i 번째 물건의 가치

W[i] - i번째 물건의 무게

 

두가지 경우로 생각해 볼 수 있는데 

1) i번째 물건을 챙긴 경우

 D[i][j] = D[i-1][j-w[i]] + v[i]

 

2) i번째 물건을 챙기지 x 경우

 D[i][j] = D[i-1][j]

 

 

c++ 코드 :

//
//  12865_nomal_back.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/09.
//

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
//DP - KnapSack

int d[101][100001]; // i번째 물건까지 사용하여 k 용량의 가방에 물건 채울때까지 최대 가치
int W[101]; //W - i 번째 물건의 무게
int V[101]; //V - i 번째 물건의 가치


int N, K;

//i 번째 물건 담은 경우 d[i-1][j-W[i]] + V[i]
//담지 않은 경우 d[i-1][j]
//모둔 j에 대해 max 찾기

void find_max_value(int N, int K){
   
    for(int i = 1; i <= N; i++){ // 배낭 물건 돌기
        for(int j = 1; j <= K; j++){
            d[i][j] = d[i-1][j];
            if(j - W[i] >= 0){ //무게가 남아서 돌 수 있을 때
                d[i][j] = max(d[i][j], d[i-1][j - W[i]] + V[i]);
                
            }
        }
        
    }
    cout << d[N][K] << '\n';
}


int main(){
            
    scanf("%d %d", &N, &K);
    memset(d, 0, sizeof(d));
    
    for(int i = 1; i <= N; i++){
        int weight, value;
        scanf("%d %d", &weight, &value);
        W[i] = weight;
        V[i] = value;
        
    }
    
    find_max_value(N, K);
    return 0;
}