[Algorithm] 0-1 Knapsack Problem

(VS 라이센스가 만료되어 웹 C++에서 개발함 ㅠㅠ www.onlinegdb.com/online_c++_compiler)

ref. reakwon.tistory.com/34

 

0. Knapsack

 도둑이 가방의 용량제한 안에서 최대한 가치를 갖도록 물건을 조합해서 넣는 문제이다.

어려울 것 없이 '1. 훔친다(goto next)+현재Value' 와 '2.안훔친다(goto next)' 두 step으로 계속해서 재귀문을 돌리면 된다.

 

 

1. 일반코드.

Knapsack은 sub fcn에서 '훔치냐' '안훔치냐' 두 개의 재귀를 호출하고, 그 중 큰 값을 return하면 된다.

 

#include <iostream>
 
using namespace std;
#define MAX(a,b) ((a)>(b)?(a):(b))
 
#define WEIGHT 0
#define VALUE 1
#define N 5
int items[N][2] = {
    {10, 1},
    {1, 1},
    {5, 3},
    {4, 2},
    {8, 1},
};
 
int knapsack(int n, int cap) {
    if(n==N) 
        return 0; // 마지막은 선택한게 없으므로 0값
    
    int ret =0;
    if(items[n][WEIGHT] <= cap) // 용량이 가능하다면
        ret = knapsack(n+1, cap - items[n][WEIGHT]) + items[n][VALUE]; 
        // 훔쳤을때. 훔친sub fcn결과와 현재 훔친물건 value 더함
    int ret2 = knapsack(n+1, cap); // 안훔쳐
    return MAX(ret, ret2); // 현재 시점에서 훔/안훔 중 큰 놈으로 ret
}
 
int main()
{
    cout<<"Hello World";
 
    //for(int i =0; i < 3; i++)
    int rst = knapsack(0, 100);
    cout<<rst;
 
    return 0;
}
 

 

 

2. DP 추가

 단순하게 N번 ITEM이 특정 CAPACITANCE 의 상황일 때 Value를 연산한 기록 있다면 해당 값을 바로 return한다.

아래의 코드와 같이 DP배열을 하나 추가해서 사용하자.(초기화값은 -1)

 

 
#include <iostream>
using namespace std;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
 
#define WEIGHT 0
#define VALUE 1
#define N 5
int items[N][2] = {
    {10, 1},
    {1, 1},
    {5, 3},
    {4, 2},
    {8, 1},
};
 
#define MAX_CAP 1000 // capacity max에 맞도록 dp배열 생성하기 위함
int dp[N][MAX_CAP]; // dp용 배열(N번 item이 CAP일때 이미 계산기록이 있으면 
                    // 그대로 활용함)
 
int knapsack(int n, int cap) {
    if(n==N) 
        return 0; // 마지막은 선택한게 없으므로 0값
    
    //int ret =0; // dp없을때
    /*******************************************/
    int ret = dp[n][cap]; // **** dp배열에 n이 cap일때 미리 계산된 값 있음?
    if(ret != -1) return ret; // **** dp값 return
    /*******************************************/
    
    if(items[n][WEIGHT] <= cap) // 용량이 가능하다면
        ret = knapsack(n+1, cap - items[n][WEIGHT]) + items[n][VALUE]; 
        // 훔쳤을때. 훔친sub fcn결과와 현재 훔친물건 value 더함
    int ret2 = knapsack(n+1, cap); // 안훔쳐
    ret = MAX(ret, ret2);// 현재 시점에서 훔/안훔 중 큰 놈으로 ret
    
    /*******************************************/
    dp[n][cap] = ret; // **** dp에 value write
    /*******************************************/
    
    return ret;
}
 
int main()
{
    /*******************************************/
    // dp init
    for(int i = 0; i < N; i++)
        for(int j = 0; j < MAX_CAP; j++)
            dp[i][j] = -1;
    /*******************************************/
    
    int rst = knapsack(0, 100);
    cout<<rst;
 
    return 0;
}