背包问题-动态规划

问题描述：

背包的最大容量为W,有N件物品，每件物品重量为w,价值为p，怎样选择物品能使得背包里的物品价值最大？

输入：

10 3 (W,N)

4 5 (w,p)

6 7 (w,p)

8 9 (w,p)

#include <stdio.h>#define THING   20#define WEIGHT  100int arr[THING][WEIGHT]; /* 背包容量为weight，依次尝试1 - thing 物品时的最大价值 */int price[100]; /* 物品价格表 */int weight[100]; /* 物品重量表 */int main(){    int i,j;    int max_weight,max_thing;    /* 初始化 */    for(i = 0 ; i < THING ; ++i)    {        for(j = 0 ; j < WEIGHT ; ++j)            arr[i][j] = 0;    }    /* 读入数据 */    scanf("%d%d",&max_weight,&max_thing);    for(i = 1 ; i <= max_thing ; ++i)    {        scanf("%d%d",&weight[i],&price[i]);    }    /* 计算 */    for(i = 1 ; i <= max_thing ; ++i)    {        for(j = 1 ; j <= max_weight ; ++j)        {            if(j >= weight[i]) /* 如果当前物品的容量小于背包容量（当前物品能放进去） */            {                /* 如果当前物品的价值 + 背包剩余空间能放进去的物品价值(之间计算过的最佳方案) */                /* 大于上一次选择的价值，则放入当前物品 */                if(price[i] + arr[i - 1][j - weight[i]] > arr[i - 1][j])                    arr[i][j] = price[i] + arr[i - 1][j - weight[i]];                else /* 否则继续沿用上次的选择 */                    arr[i][j] = arr[i - 1][j];            }            else /* 当前物品放不进去，继续沿用上次的选择 */                arr[i][j] = arr[i - 1][j];        }    }    /* 输出最优解 */    printf("max weight : %d\n",arr[max_thing][max_weight]);    /* 输出所有子解 arr[][] */    for(i = 0 ; i <= max_thing ; ++i)    {        for(j = 0 ; j <= max_weight ; ++j)            printf("%3d",arr[i][j]);        printf("\n");    }    return 0;}