完全背包
完全背包
曾劲松 发表于2年前
完全背包
  • 发表于 2年前
  • 阅读 13
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

http://blog.csdn.net/insistgogo/article/details/11081025

1、问题描述

    已知:有一个容量为V的背包和N件物品,第i件物品的重量是weight[i],收益是cost[i]。

    条件:每种物品都有无限件,能放多少就放多少。

    问题:在不超过背包容量的情况下,最多能获得多少价值或收益

  1. 直接扩展01背包的方程

  2. /*
    f[i][v] = max(f[i - 1][v],f[i - K * weight[i]] + K * Value[i]);
     其中  1 <= K * weight[i] <= v,(v指此时背包容量)  
    //初始条件  
    f[0][v] = 0;  
    f[i][0] = 0; 
    */
    
    const int N = 3;  
    const int V = 5;  
    int weight[N + 1] = {0,3,2,2};  
    int Value[N + 1] = {0,5,10,20};  
      
    int f[N + 1][V + 1] = {0};  
      
    int Completeknapsack()  
    {  
        //边界条件  
        for (int i = 0;i <= N;i++)  
        {  
            f[i][0] = 0;  
        }  
        for (int v = 0;v <= V;v++)  
        {  
            f[0][v] = 0;  
        }  
        //递推  
        for (int i = 1;i <= N;i++)  
        {  
            for (int v = 1;v <= V;v++)  
            {  
                f[i][v] = 0;  
                int nCount = v / weight[i];  
                for (int k = 0;k <= nCount;k++)  
                {  
                    f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);  
                }  
            }  
        }  
        return f[N][V];  
    }   

    复杂度分析:程序需要求解N*V个状态,每一个状态需要的时间为O(v/Weight[i]),总的复杂度为O(NV*Σ(V/c[i]))。

    代码优化:完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。

    即,如果一个物品A是占的地少且价值高,而物品B是占地多,但是价值不怎么高,那么肯定是优先考虑A物品的。

  3. 普通拆分V/Weight[i]

  4. 二进制拆分

  5. const int N = 3;  
    const int V = 20;
    int weight[N + 1] = {0,3,2,2};  
    int Value[N + 1] = {0,5,10,20};  
      
    int NNew = 0;  
    vector<int> weightVector;  
    vector<int> Valuevector;  
    int f[V + 1] = {0};  
    /*拆分物品*/  
    void SplitItem()  
    {  
        //从1开始  
        weightVector.push_back(0);  
        Valuevector.push_back(0);  
        //开始拆分  
        int nPower = 1;  
        for (int i = 1;i <= N;i++)  
        {  
            nPower = 1;  
            while (nPower * weight[i] <= V)  
            {  
                weightVector.push_back(nPower * weight[i]);  
                Valuevector.push_back(nPower * Value[i]);  
                nPower <<= 1;  
            }  
        }  
    }  
      
    int Completeknapsack()  
    {  
        //拆分物品  
        SplitItem();  
        //转化为01背包处理  
        NNew = weightVector.size() - 1;//多加了一个0,要减去  
      
        for (int i = 1;i <= NNew;i++)//物品个数变化  
        {  
            for (int v = V;v >= weightVector[i];v--)//背包容量仍是V  
            {  
                f[v] = max(f[v],f[v - weightVector[i]] + Valuevector[i]);  
            }  
        }  
      
        return f[NNew];  
    }  

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 4
博文 132
码字总数 141022
×
曾劲松
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: