[DP] 0-1 배낭문제 (Knapsack)

0-1 배낭문제에 대한 동적 계획법 1,2,3 알고리즘을 구현하고 다음 예제에 적용하시오.
배낭의 크기는  13 이고 , 물건의 크기와 이익은 다음 표와 같다. 

    

i	P i	W i
1	4	2
2	6	4
3	8	5
4	9	8
5	6	3

#include <iostream>
 
using namespace std;
 
int W[6] = { 0,2,4,5,8,3 }; //물건들의 무게
int P[6] = { 0,4,6,8,9,6 }; //물건들의 이익
int K[6][14]; //가방
 
int max(int arr1, int arr2) //큰 수 비교
{
    return (arr1 > arr2) ? arr1 : arr2;
}
 
int bag_ks_DP(int n, int M) //동적계획법 1
{
    int i, w;
 
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= M; w++)
        {
            if (i == 0 || w == 0)
            {
                K[i][w] = 0;
            }
            else if (w < W[i])
            {
                K[i][w] = K[i - 1][w];
            }
            else
            {
                K[i][w] = max(K[i - 1][w], K[i - 1][w - W[i]] + P[i]);
            }
        }
    }
    return K[n][M];
}
 
void printTable() //배열 출력
{
    for (int i = 0; i < 6; i++)
    {
        cout << i << ": ";
        for (int w = 0; w < 14; w++)
        {
            cout.width(3);
            cout << K[i][w];
        }
        cout << endl;
    }
}
 
int main()
{
    int n = 5, M = 13; //물건 개수 5개, 배낭무게 13
 
    int big_money = bag_ks_DP(n, M);
    printTable();
    cout << "최대 이익은 " << big_money << " 입니다" << endl;
 
    return 0;
}

0-1배낭문제.hwp

01_bag_1.cpp

01_bag_2.cpp

01_bag_3.cpp