实数01背包

问题描述

大家所熟知的01背包中要求输入是一个实数，两个整数，即背包容量和物品体积都是整数，而物品价值可以是实数，这时可以对这个整数部分即体积进行枚举，实现动态规划，即将前i个物品装入容量为j的背包所能的最大价值为dp[i][j]=max(dp[i-1][j],dp[i-1][j-v(i)]+w(i))，这个方法至少有两个局限，

1、由于该算法的时间复杂度为O（i*j），i为物品个数，j为背包容量，此时当物品数量并不多本应该是个简单问题的时候，却往往由于背包容量过大而导致时间复杂度很高，
2、由于背包容量j和每个物品的物品体积v(i)都被用作了下标，所以被限制为整数，在很多情况下，如果出现小数，常见的做法是将小数按比例放大，将其转换为一个整数的背包问题，但对于高精度的，或个别数据高精度的情况很显然不能用这种方法，

以下是王晓东《算法设计与分析》书中的一个实数背包问题及其算法思考

算法思考;

设二元数组集p，初值为p={(0,0)}，代表装入0个物品，但用背包容量为0，拥有价值为0，之后对所有物品进行枚举，将枚举到的物品的体积加在容量上边，将价值加在整体价值上边，构成一个我们假象的讲该物体装入背包后的效果即二元数组集q={p+(v(i),w(i))}，其中如果出现整体体积已经大于背包容量的情况就将其舍弃，同时由于我们无法保证我们确实要把这个物品装入背包，于是我们保留了原有的该物体未装入背包的情况p，然后将p与q组成并集，这就代表了当前所有情况，接着我们重复上述步骤进行下一个物品的枚举，直到所有物品都枚举完毕，我们便得到了最优解。同时，这里边有一个重要的剪枝，就是如果我们能以更小的体积获得更大的价值那么那个用了更多体积却只得到更少价值的情况就可以剪枝了，即如果存在两个二元组（a,b），（c,d），满足a<=c && b>d，那么二元组（c,d）可以舍弃，具体例子如下：

起始状态为（0，0），放入一个新的物体后，产生一些新的状态。

容量为10，有5个物体，重量为3 5 1 9 7，价值为11 28 6 49 35。则二元组集p的变化为

加入第1个物体时
p={(0,0),(3,11)}
加入第2个物体时
p={(0,0),(3,11),(5,28),(8,39)}
加入第3个物体时
p={(0,0),(1,6),(4,17),(5,28),(6,34),(8,39),(9,45)}
加入第4个物体时
p={(0,0), (1,6),(4,17),(5,28),(6,34),(8,39),(9,49),(10,55)}
加入第5个物体时
p={(0,0), (1,6),(4,17),(5,28),(6,34), (7,35) ,(8,39), (9,49),(10,55)}

剪枝1：已放物体的总重量超过背包体积，剪枝
剪枝2：存在(Ai,Bi),(Aj,Bj),如果Ai=Bj,剪掉后一个。

根据剪枝：将物体按体积从大到小排序，价值从大到小排序。

关于该算法的时间复杂度，应该是O（2n ），如王晓东书上所说，集合p是通过对物品枚举放入背包与否的所有状态的一种展示，最坏是2n ，即每一个物品都不满足剪枝条件，集合p会指数级的扩张，但是这种情况应该是极少数吧，正如网上所流传的，传说这个算法的平均时间复杂度是n2.4 。

代码实现

//算法实现，迥异于王晓东书上的那段诡异的代码。。。。。。
#include <stdio.h>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
double cost[1000];
double value[1000];
int n,v;
struct point{
    double capacity;
    double worth;
    point(double a=0,double b=0){capacity=a;worth=b;}
};
list<point> p;
list<point> q;
list<point> r;
void ptoq(int i)
{
    q.clear();
    list<point>::iterator it;
    double tempcap;
    double tempval;
    for(it=p.begin();it!=p.end();++it)
    {
        tempcap=(*it).capacity+cost[i];
        tempval=(*it).worth+value[i];
        point temp(tempcap,tempval);
        if(tempcap<=v)
            q.push_back(temp);
    }
}
void marriage()
{
    r.clear();
    list<point>::iterator itp,itq;
    itp=p.begin();
    itq=q.begin();
    while(itp!=p.end() && itq!=q.end())
    {
        if((*itp).capacity>(*itq).capacity)
        {
            if(r.empty() || (*itq).worth>r.back().worth)
                r.push_back(*itq);
            itq++;
        }
        else if((*itp).capacity<(*itq).capacity)
        {
            if(r.empty() || (*itp).worth>r.back().worth)
                r.push_back(*itp);
            itp++;
        }
        else
        {
            if((*itp).worth>(*itq).worth)
            {
                if(r.empty() || (*itp).worth>r.back().worth)
                    r.push_back(*itp);
            }
            else
            {
                if(r.empty() || (*itq).worth>r.back().worth)
                    r.push_back(*itq);
            }
            itq++;
            itp++;
        }
    }
    while(itp!=p.end())
    {
        if(r.empty() || (*itp).worth>r.back().worth)
            r.push_back(*itp);
        itp++;
    }
    while(itq!=q.end())
    {
        if(r.empty() || (*itq).worth>r.back().worth)
            r.push_back(*itq);
        itq++;
    }
    p=r;
}
int main()
{
    int i;
    scanf("%d%d",&n,&v);
    for(i=1;i<=n;++i)
        scanf("%lf%lf",&cost[i],&value[i]);
    point tmp(0,0);
    p.push_back(tmp);
    ptoq(1);
    for(i=2;i<=n;++i)
    {
        marriage();
        ptoq(i);
    }
    marriage();
    printf("%lf",p.back().worth);
    return 0;
}