Knapsack Problem

Knapsack Problem

Knapsack Problem의 정의

예를 들어 다음과 같은 option이 있고 이에 대한 Cost 와 Expected reach가 있다고 하자. 주어진 예산이 W가 될 것이고, Cost는 정의에서 w가 될 것이고 Expected reach는 p가 된다.

Knapsack에서는 정해진 W를 넘지 않은 채로,  Expected reach를 최대화 하는 것이 목적이다.

간단히 말하자면 주어진 예산 안에서 사람들이 최대한 많이 볼 수 있게 하는 것이 목적이다.

---

Dynamic programming approach

P(i,w)를 maximized profit, A*를 optimal subset이라고 가정하자.

그렇게 되면 위 처럼 두가지로 optimal subset에 포함되는 경우와 포함되지 않는 경우로 모든 경우의 수를 표현 할 수 있게 된다.

위를 가지고 Optimal substructure를 구현하면 다음과 같다.

 

#include <stdio.h>
#include <stdlib.h>

void PRINT_ITEM(int **Q, int *w, int n, int W, int op) {
    if (W == 0)
        return;
    if (Q[n][W] == 1) {
        PRINT_ITEM(Q, w, n - 1, W - w[n], 0);
        if (op) printf("%d\n", n);
        else printf("%d, ", n);
    }
    else
        PRINT_ITEM(Q, w, n - 1, W, 0);
}

int zero_one_knapsack(int* p, int* w, int n, int W) {
    int i, ww, tmp;
    int** P, ** Q;
    P = (int**)malloc(sizeof(int*) * (n + 1));
    Q = (int**)malloc(sizeof(int*) * (n + 1));
    for (i = 0; i <= n; i++) {
        P[i] = (int*)malloc(sizeof(int) * (W + 1));
        Q[i] = (int*)malloc(sizeof(int) * (W + 1));
    }
    for (ww = 0; ww <= W; ww++)
        P[0][ww] = 0, Q[0][ww] = 0;
    for (i = 1; i <= n; i++) {
        P[i][0] = 0, Q[i][0] = 0;
        for (ww = 1; ww <= W; ww++) {
            if (w[i] <= ww) {
                if ((tmp = p[i] + P[i - 1][ww - w[i]]) > P[i - 1][ww]) {
                    P[i][ww] = tmp;
                    Q[i][ww] = 1;
                }
                else {
                    P[i][ww] = P[i - 1][ww];
                    Q[i][ww] = 0;
                }
            }
            else {
                P[i][ww] = P[i - 1][ww];
                Q[i][ww] = 0;
            }
        }
    }
    PRINT_ITEM(Q, w, n, W, 1);
    return P[n][W];
}

int main(int argc, char* argv[])
{
    int* p, * w;
    int i, N, W;
    
    scanf("%d %d", &N, &W);
    p = (int*)malloc(sizeof(int) * (N + 1));
    w = (int*)malloc(sizeof(int) * (N + 1));
    for (i = 1; i <= N; i++) {
        scanf("%d %d", w + i, p + i);
    }
    printf("%d\n", zero_one_knapsack(p, w, N, W));

    return 0;
}