13-complex.cminus

/* 01 背包问题 */

int n;
int m;

int w[5];
int v[5];

int dp[66]; /* dp[n * 11 + size] 表示前 n 个物品放入容量为 size 的背包中的最大价值，初始化为 -1 */

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

/* 状态转移方程：
   dp[n][size] = max(dp[n - 1][size], dp[n - 1][size - w[n]] + v[n])
   边界条件：
   dp[n][size <= 0] = 0
   dp[0][size] = 0  */

int knapsack(int n, int size) {
    int result;
    if (size <= 0)
        return 0;
    if (n == 0)
        return 0;
    if (dp[n * 11 + size] >= 0)
        return dp[n * 11 + size];

    if (size < w[n - 1])
        result = knapsack(n - 1, size);
    else
        result = max(knapsack(n - 1, size), knapsack(n - 1, size - w[n - 1]) + v[n - 1]);

    dp[n * 11 + size] = result;
    return result;
}

int main(void) {
    int i;
    i = 0;

    n = 5;
    m = 10;
    w[0] = 2;
    w[1] = 2;
    w[2] = 6;
    w[3] = 5;
    w[4] = 4;

    v[0] = 6;
    v[1] = 3;
    v[2] = 5;
    v[3] = 4;
    v[4] = 6;

    while (i < 66) {
        dp[i] = 0 - 1;
        i = i + 1;
    }

    output(knapsack(n, m));
    return 0;
}