背包问题

此处背包问题描述为：N种大小和价值不等东西，容量为M的背包，求能带走的最大价值。

可以采用直接递归做法，但是时间复杂度为指数级别，代码如下

//递归版本，指数复杂度,cap为容量
int knap(int cap)
{
    int i,t,max,space;
    for(i=0,max=0;i<N;i++)
        if((space=cap-item[i].size)>=0)
            if((t=knap(space)+item[i].value)>max)
            {
                printf("choose item %d\n",i);
                max=t;
            }
    return max;
}

采用自顶向下动态规划，可以将指数降低为线性，思想为记录中间计算过程，避免重复计算。

//自顶向下动态规划
int maxKnown[M]={unknown};
int itemindexKnown[M]={unknown};//可要可不要
int dynamic_knap(int m)
{
    int i,space,max,maxi,t;
    if(maxKnown[m]!=unknown)
        return maxKnown[m];

    for(i=0,max=0;i<N;i++)
        if((space=m-item[i].size)>=0)
            if((t=dynamic_knap(space)+item[i].value)>max
            {
                printf("choose item %d\n",i);
                max=t;
                maxi=i;
            }
    maxKnown[m]=max;
    itemindexKnown[m]=maxi;
    return max;
}

更多背包问题:

http://www.concretevitamin.com.cn/informatics/Pack/Index.html