背包有关问题-动态规划

背包问题-动态规划

问题描述：

背包的最大容量为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  100

int 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;
}