0/1背包问题

1. 蛮力法

伪代码:

输入:重量{W1,W2,----Wn},价值 {V1,V2,---Vn},背包容量C
输出:装入背包的物品编号和最大价值

1. 初始化最大价值maxValue=0;结果子集S=Φ;
2. 对集合{1,2,---,n}的每个子集T,执行下述操作;
   2.1 初始化背包的价值value=0;背包的重量weight=0;
   2.2 对子集T的每一个元素;
       2.2.1 如果weight+Wj<C,则weight=weight+Wj;value=value+Vj
       2.2.2 否则,转步骤2考察下一子集
3. 输出子集S中的各元素和最大价值maxValue;

算法效率:Ω(2^n)

2. 动态规划法

算法实现:

int KnapSack(int w[],int v[],int n,int C)
{
    int i,j;
    for(i=0; i<=n; i++) // 初始化第0列
        V[i][0]=0;
    for(j=0; j<=C; j++) // 初始化第0行
        V[0][j]=0;
    //计算第i行,进行第i次迭代
    for(i=1; i<=n; i++)
        for(j=1; j<=C; j++)
            if(j<w[i])
                V[i][j]=V[i-1][j];
            else
                V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
    // 求装入背包的物品
    for(j=C, i=n; i>0 ;i--)
    {
        if(V[i][j]>V[i-1][j])
        {
            x[i]=i;
            j=j-w[i];
        }
        else 
            x[i]=0;
    }
    return V[n][C]; //返回背包取得的最大价值
}
/* 
    设n个物品的重量存储在数组w[n]中,价值存储在数组v[n]中;
    背包的容量为C,数组V[n+1][C+1]存放迭代结果,其中V[i][j]表示前i个物品装入容量为j的背包中获得的                
    最大价值,数组x[n]存储装入背包的物品
*/

时间复杂性:O(n*C);

3. 分支限界法

伪代码:

输入: 重量{W1,W2,----Wn},价值 {V1,V2,---Vn},背包容量C
输出: 背包获得的最大价值和装入背包的物品

1. 根据限界函数计算目标函数的上界up;采用贪婪法得到下界down;
2. 根据根结点的目标函数值并加入待处理结点表PT;
3. 循环直到某个叶子节点的目标函数值在表PT中取得的最大值
   3.1 i=表PT中具有最大值的结点;
   3.2 对节点i的每个孩子结点x执行以下操作:
       3.2.1 如果结点x不满足约束条件,则丢弃该节点;
       3.2.2 否则估算结点x的目标函数值lb,将结点x将入表PT中;
4. 将叶子结点对应的最优值输出,回溯求得最优解的各个分量.



/* 
    设n个物品的重量存储在数组w[n]中,价值存储在数组v[n]中;
    背包的容量为C,数组V[n+1][C+1]存放迭代结果,其中V[i][j]表示前i个物品装入容量为j的背包中获得的                
    最大价值,数组x[n]存储装入背包的物品
*/