文档章节

完全背包

曾劲松
 曾劲松
发布于 2016/08/04 22:36
字数 552
阅读 13
收藏 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];  
    }  

 

© 著作权归作者所有

曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问

暂无文章

docker中部署的应用,获取含有中文字符的验证码图片时无法正常显示

使用docker过程中遇过的最诡异的问题,服务在本地环境中,通过在IDEA里面运行,或者使用java -jar ***.war运行,获取验证码图片都没有问题,但是运行在docker中,图片正常返回,但是上面的汉...

莫在全
27分钟前
1
0
postgres+socket.io+nodejs实时地图应用实践

nodejs一直以异步io著称,其语言特性尤其擅长于在realtime应用中,如聊天室等。在进行实时应用开发时,必不可少的需要用到 socket.io库,可以说,nodejs+socket.io在实时应用中具有较好的表现...

dragon_tech
33分钟前
2
0
Java开发面试题汇总

目前流行的开发技术、常见的面试问题以及问题的答案都已经写的特别清楚了,今天我在之前的基础上,再基于个人的经验继续精选一些面试题给大家阅读参考。 1,Java的反射 Java 反射机制是在运行...

花漾年华
38分钟前
5
0
聊聊flink jdbc的ParameterValuesProvider

序 本文主要研究一下flink jdbc的ParameterValuesProvider ParameterValuesProvider flink-jdbc_2.11-1.8.0-sources.jar!/org/apache/flink/api/java/io/jdbc/split/ParameterValuesProvide......

go4it
38分钟前
1
0
UserInputControls用户输入控制

enum UserInputControls { kGovernedByOrthoMode = 0x0001,//正交模式管理 kNullResponseAccepted = 0x0002,//允许输入空 kDontEchoCancelForCtrlC = 0x0004,//ctrl C 模式不能重复......

一个小妞
59分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部