01背包问题

题目：容量为9的背包，有4种物品，体积分别为2，3,4,5，价值分别为3,4,5,7，求能放进背包的最大值。

#include <iostream>
using namespace std;

#define MAXSIZE 9
#define NUM 4

int main(void)
{
    int size_value[5][2] = { {0,0},{2,3},{3,4},{4,5},{5,7} };
    int solution[NUM + 1][MAXSIZE +1];

    for(int p=0;p<=NUM;p++)
    {
        for (int q=0;q<=MAXSIZE;q++)
        {
            solution[p][q]=0;
        }
    }

    for(int i = 1;i <=NUM;i++)
    {
        for (int j = 0;j<=MAXSIZE;j++)
        {
            solution[i][j] = solution[i-1][j];
            if(size_value[i][0] <= j )
            {
                if(solution[i-1][j] < (solution[i-1][j-size_value[i][0]] + size_value[i][1])) 
                   solution[i][j] =  solution[i-1][j-size_value[i][0]] + size_value[i][1];             
            }
       }
    }

    for(int p=0;p<=NUM;p++)
    {
        for(int q=0;q<=MAXSIZE;q++)
       {
           cout<<solution[p][q]<<" ";
       }
       cout<<"\n";
    }
    cout<<"The Max Value is : "<<solution[NUM][MAXSIZE];
    while(1);
    return 0;
}


关于动态规划的算法，一定要在纸上画出计算公式。
关于此算法要注意的一点是：4个物品，最好定义一个5行2列的数组，后面就能与solution[NUM][MAXSIZE}对应上，关于i+1,i,i-1的问题要尤其注意

评论

1 楼 wukunlsy 2011-10-20