文档章节

完全背包

曾劲松
 曾劲松
发布于 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];  
    }  

 

© 著作权归作者所有

共有 人打赏支持
曾劲松
粉丝 4
博文 198
码字总数 141022
作品 0
武汉

暂无文章

Thinkphp5 优雅配置两个数据库

工作需要需要配置两个数据库,框架5.0的,步骤如下: 1、在database.php同级创建一个database2.php文件 在里面配置第二个数据库信息, 2、在config中配置这个数据库信息: 3、创建第二个表的...

wqzbxh
25分钟前
2
0
Socket网络编程进阶与实战

Socket网络编程进阶与实战 Socket对于每个工程师的重要性不言而喻。本课程将理论结合实践,带你从零开始,系统学习Socket编程技术,让Socket的学习不再那么零散与难以掌握,同时会提炼出Soc...

qq__2304636824
31分钟前
2
0
Android studio常用快捷键

Ctrl +Alt +Space //显示可用参数 Ctrl + Alt +M //抽取方法 Ctrl +Alt + F //提取全局变量 Ctrl +Shift + "+或-" //折叠/展开代码块 Shift + F6 //批量更改变量 Ctrl + Tab //切换器 Ctrl +...

lanyu96
43分钟前
2
0
@ControllerAdvice 拦截异常并统一处理

在spring 3.2中,新增了@ControllerAdvice 注解,可以用于定义@ExceptionHandler、@InitBinder、@ModelAttribute,并应用到所有@RequestMapping中。 一、介绍 创建 MyControllerAdvice,并添...

狼王黄师傅
47分钟前
2
0
ajax传递参数给springmvc总结[转]

https://www.cnblogs.com/franson-2016/p/6770028.html https://www.cnblogs.com/xiaoxi/p/5708084.html 总结: 1.springmvc与Ajax交互,可以传入三种类型的数据: (1)文本:"uname=alice&......

废柴
49分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部