题目如下:
一个容量为capacity的背包,有n个物品,每个物品都有其价值和重量,把物品放入背包中,只要重量和少于capacity就可以,要求使背包中物品的价值总和最大,求这个最大值( 重量和价值都是正整数)

可以分别考虑对重量和价值进行动态规划处理:
#include <stdio.h>
#include <stdlib.h>
#define FINITE ( 0x3fffffff )

typedef int Weight;

/* 对价值进行处理的方法 */

int Knapsack( const Weight weight[],       // 重量数组
              const int value[],           // 价值数组
              int n,                       // 物品个数
              Weight capacity )            // 背包容量
{
    int i, j, k, max;

    for ( i = 0, max = 0; i < n; ++i )
    {
        max += value[i];
    }
    Weight* present = ( Weight* )malloc( ( max + 1 ) * sizeof( Weight ) );
    Weight* previous = ( Weight* )malloc( ( max + 1 ) * sizeof( Weight ) );
    Weight* tmp;

    for ( i = 0; i <= max; ++i )
    {
        present[i] = ( i <= value[0] ? weight[0] : FINITE );
    }
    for ( i = 1; i < n; ++i )
    {
        tmp = present;
        present = previous;
        previous = tmp;
        for ( j = max; j >= 0; --j )
        {
            present[j] = previous[j];
            k = j + value[i];
            if ( k <= max && previous[j] + weight[i] < present[k] )
            {
                present[k] = previous[j] + weight[i];
            }
        }
    }

    for ( i = max; i > 0 ; --i )
    {
        if ( present[i] <= capacity )
        {
            break;
        }
    }
    free( present );
    free( previous );
    return i;
}

typedef int Value;

/*对重量处理的方法*/

Value Knapsack2( const int weight[],     // 重量数组
                 const Value value[],    // 价值数组
                 int n,                  // 物品个数
                 int capacity            // 背包容量
                )
{
        Value* previous = ( Value* )malloc( ( capacity + 1 ) * sizeof( Value ) );
        Value* present  = ( Value* )malloc( ( capacity + 1 ) * sizeof( Value ) );
        Value* temp = NULL;
        Value max_value;
        int i, j, k;

        for ( j = 0; j <= capacity; ++j )
        {
                previous[j] = ( j < weight[0] ? 0 : value[0] );
        }
        for ( i = 1; i < n; ++i )
        {
                for ( j = 0; j <= capacity; ++j )
                {
                        present[j] = previous[j];
                        k = j - weight[i];
                        if ( k >= 0 && previous[k] + value[i] > present[j] )
                        {
                                present[j] = previous[k] + value[i];
                        }
                }
                temp = present;
                present = previous;
                previous = temp;
        }
        max_value = previous[capacity];
        free( previous );
        free( present  );
        return max_value;
}

int main( void )
{
        Weight weight[] = { 100, 14, 10 };
        Value value[] = { 20, 18, 19 };

        printf( "%d\n", Knapsack( weight, value, 3, 116 ) );
        system( "pause" );
        return 0;
}