[ 算法 ] 0-1背包问题

问题

有N件物品和一个容量为C的背包。放入第i件物品耗费的空间是_wi_，得到的价值是_vi_。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。

代码

#include <stdio.h>

//找出最大价值
#define mmax(a,b)   (a)>(b)?(a):(b)

int m[2][1000001];
int knap(int n, int c, int* w, int* v)
{
    int i, j;

    //初始化数组
    for (i = 0; i <= n; i++)
    {

        m[i % 2][0] = 0;
        m[0][i] = 0;

    }

    //n个物品依次放入背包
    for (i = 1; i <= n; i++)
    {
        //状态记录
        int newl = i % 2; //新的状态
        int oldl = (i + 1) % 2; //旧状态

        //背包容量
        for (j = 1; j <= c; j++)
        {
            //当前背包的容量大于所装物品的重量
            if (j >= w[i])
            {
                //对所装入的物品的价值进行判断
                //1.当前物品放入价值不大于上一个状态的物品价值则保持上一个物品的价值
                //2.当前物品放入价值大于上一个状态的物品价值且背包剩余空间不足以放下物品则替换背包中的物品;其次，当物品重量足以放下且与上一个物品共存则价值等于上一个物品的价值+当前物品的价值
                m[newl][j] = mmax(m[oldl][j], m[oldl][j - w[i]] + v[i]); //状态转移方程
            }
            else
            {
                //当装入的物品质量大于背包所剩容量则保持上一个状态物品的价值不变
                m[newl][j] = m[oldl][j];
            }
        }
    }

    return m[n % 2][c];
}

int main(void)
{
    //N 物品数量  C背包容量
    //w[] 物品质量  v物品的价值
    int N, C, w[1001], v[1001];

    scanf("%d %d", &N, &C);

    for (int i = 1; i <= N; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= N; i++) scanf("%d", &v[i]);
    int res = knap(N, C, w, v);
    printf("%d", res);
    return 0;
}