动态规划解背包问题

这个问题也可以用动态规划的分阶段决策方法，来确定把哪一个物体装入背包的最优决策，假定背包的载重量范围是0-m，类似资源分配那样，另optpi[j]表示在前i个物体中，能够装入重量为i的背包的物体的最大价值，j=1,2,3.......m.显然，此时在前i个物体中，有些物体可以装入背包，有些物体不能装入背包。于是，可以得到下面的动态规划函数：

6.6.1表面：把前i个物体装入载重量为0的背包，或把0个物体装入载重量为j的背包，得到的价值都是0.

6.6.2表面：

如果第i个物体的重量大于背包的载重量,则等于optp[i-1][j].

如果j>=wi.

optp[i-1](j-wi)+pi 表面：当第i个物体的重量小于背包载重量时，如果把第i个物体装入载重量为j的背包，则背包中物体的价值==

等于把前面i-1个物体装入载重量为j-wi的背包所得到的的价值+加上第i个物体的价值pi。

如果第i个物体没有装入背包，则背包中物体价值就等于把前面第i-1个物体装入载重量为j的背包中所取得的价值。

显然，这2种装入方法，取的的价值不一定相同。因此，取最大值。

#include<iostream>
#include<climits>
#include<iomanip>
using namespace std;

typedef struct{
    float p;
    float w;
    float v;
}Object;
Object object[7];//7个物品

float knapsack(int w[],float p[],int m,int n,bool x[ ])
{
    float **optp=new float*[n+1];
    for(int i=0;i<=n;i++)
        optp[i]=new float[m+1];

    for(int i=0;i<=n;i++)
    {
        optp[i][0]=0;
        x[i]=false;
    }
    for(int i=0;i<=m;i++)
        optp[0][i]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j<w[i])
            {
                optp[i][j]=optp[i-1][j];
                 
            }
            else
            {
                int  tmp1=optp[i-1][j];
                 int tmp2=optp[i-1][j-w[i]]+p[i];
                 if(tmp1>=tmp2)
                 {
                     optp[i][j]=tmp1;
                      
                 }
                 else
                 {
                     optp[i][j]=tmp2;
                     
                 }

     
            }
        }//end inner for
    }
    int j=m;//递推装入背包的物体
    for(int i=n;i>0;i--)
    {
        if(optp[i][j]>optp[i-1][j])
        {
            x[i]=true;
            j=j-w[i];
        }
    }
     
    return optp[n][m];

}

int main()
{
    int M=10;
     
    float pArr[]={0,6,3,5,4,6};
    int wArr[]={0,2,2,6,5,4};
     
    bool x[6];
    cout<<"各个物品价值为"<<endl;
    for(int i=1;i<=5;i++)
        cout<<left<<setw(2)<<pArr[i]<<ends;
    cout<<endl<<"各个重量"<<endl;
    for(int i=1;i<=5;i++)
        cout<<left<<setw(2)<<wArr[i]<<ends;
    cout<<endl;
    cout<<"最大价值为"<<knapsack(wArr,pArr,M,5,x)<<endl;
    cout<<"解为"<<endl;
    for(int i=1;i<=5;i++)
        cout<<x[i]<<ends;
    cout<<endl;
     

}

注意我们的pArr[]和wArr[]第0个都应该不存，与上面的knapsack对应：

float pArr[]={0,6,3,5,4,6};
    int wArr[]={0,2,2,6,5,4};
这点要特别注意，否则很容易出错。

for(int j=1;j<=m;j++)里面的代码：

 if(j<w[i])
            {
                optp[i][j]=optp[i-1][j];
                 
            }
            else
            {
                int  tmp1=optp[i-1][j];
                 int tmp2=optp[i-1][j-w[i]]+p[i];
                 if(tmp1>=tmp2)
                 {
                     optp[i][j]=tmp1;
                      
                 }
                 else
                 {
                     optp[i][j]=tmp2;
                     
                 }

     
            }

可以简化为:

optp[i][j]=optp[i-1][j];
if( (j>=w[i]) && optp[i-1,j-w[i]] + p[i] >optp[i-1][j];
   optp[i][j]=optp[i-1][j-w[i]] + p[i];

数据是郑宗汉这本书上的。

float pArr[]={0,6,3,5,4,6};
    int wArr[]={0,2,2,6,5,4};

用1个(n+1)*(m+1)的表，来存放前面i个物体装入载重量为j的背包时，所能取得的最大价值。

程序输出结果：

结果正确。
算法导论上的伪代码：

关于复杂度的一个问题？上面的代码复杂度是O(nw)吗？其实这里忽略的问题是，在上面的程序中n才是输入规模，而W并不是输入规模，因为它是背包的容量，而背包的数量一直都是为1的，如果在物品数量为n的情况下，背包的容量为2^n，那么这个算法的复杂度就是O(n*2^n), 所以这个问题是NP难的。


背包貌似不适用普通的线性规划，应该视为整数规划，可以认为是一个0-1规划模型。

而整数规划或0-1规划似乎没有多项式解法

背包问题的输入input = logC（C的二进制字长），这样DP复杂度对应于输入是theta（n*
2^input）。所以是np的。所以称背包问题的DP解法是伪多项式复杂度。 （容量可以很大）。
wikipedia定义：

在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。由于N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。

一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题。

在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的素数2开始，到 $sqrt{N}$ 为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约 $sqrt{N}$ 次整数除法，即其时间复杂度为 $O(sqrt{N})$ ，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的幂，因此素性测试问题的时间复杂度用D表示应为 $O(2^D)$ 。因此，上述算法是一个伪多项式时间算法。

其它被证明只具有伪多项式时间算法解的问题有背包问题，子集合加总问题。

参考：http://www.cnblogs.com/justinzhang/archive/2012/04/10/2441199.html