背包问题（一）——01背包

01背包问题

问题描述

有N件物品和一个容量为C的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的总重量和不超过背包容量，且价值总和最大。

问题分析

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

假如前k个物品放入背包容量c的背包中，可以获取最大价值是fv(k, c), 那么单独考虑第k个物品：
        如果k放入背包中，那么此背包的价值 = 前k-1个物品放入背包容量为c-w[k]所获取最大价值 + v[k]
        如果k不放入背包中，那么此背包的价值 = 前k-1个物品放入背包容量为c所获取的最大价值
即：
fv(k, c) = MAX{fv(k-1, c), fv(k-1, c-w[k]) + vk}


例如，现在有物品
P1(1,3), P2(2,3), P3(2,6), P4(3,8), P5(4,9)


     ^前k件物品
     |
5-4| 3  6  9  11 14 17
4-3| 3  6  9  11 14 17
3-2| 3  6  9  9  12 12
2-2| 3  3  6  6  6  6
1-1| 3  3  3  3  3  3
 ---------------------------->背包容量
       1  2  3  4  5  6


代码实现如下：

int max(int a, int b);

int findMaxValue_01Packge(int *weight, int *value, int len, int cpt)
{
    int *fvK_1; // 这里其实只需要一个数组就可以了，两个数组只是为了更清晰的看到每一层迭代过程
    int *fvK;
    int *tmp;
    int maxValue = 0;

    int i, j;

    fvK_1 = (int*)calloc(sizeof(int) * (cpt + 1));
    fvK = (int*)calloc(sizeof(int) * (cpt +1));

    if (NULL == fvK || NULL == fvK_1)
    {
        if (fvK_1)
            free(fvK_1);

        if (fvK)
            free(fvK);
        return -1;
    }
    for (i = 1; i <= cpt; i++)
    {
        if (i >= weight[0])
            fvK_1[i] = value[0];
    }

    for (j = 1; j < len; j++)
    {
        for(i = 1; i <= cpt; i++)
        {
            fvK[i] = max(fvK_1[i], (i >= weight[j] ? value[j] + fvK_1[i - weight[j]] : 0));
        }

        // swap fvK and fvK_1
        tmp = fvK;
        fvK = fvK_1;
        fvK_1 = tmp;
    }

    maxValue = fvK_1[cpt];

    free(fvK);
    free(fvK_1);
    return maxValue;
}