文档章节

完全背包

曾劲松
 曾劲松
发布于 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
博文 200
码字总数 141434
作品 0
武汉
私信 提问

暂无文章

Kubernetes Client-go Informer 源码分析

几乎所有的Controller manager 和CRD Controller 都会使用Client-go 的Informer 函数,这样通过Watch 或者Get List 可以获取对应的Object,下面我们从源码分析角度来看一下Client go Informe...

阿里云官方博客
24分钟前
1
0
传统IDC部署网站(三)

11. 重置密码 密钥和密码都支持远程登陆, 二选一 两个都可以登陆, 密钥相对于密码来说,相对安全一点 本地登陆无法是用密钥 修改密码 root 用户 passwd root 修改普通用户 passwd usernam...

miko0089
44分钟前
2
0
bash特性

1.支持别名 alias 2.命令替换 $(COMMANS) 或者 `COMMAND` 3. bash支持的引号: `` :命令替换 "":弱引用,可以实现变量替换 '':强引用,不实现变量替换 4.文件名通配 globbing:(man 7 glo...

忙碌的小蜜蜂
53分钟前
2
0
以语音评测的PC端demo代码为例,讲解口语评测如何实现

本文由云+社区发表 作者:腾讯智慧教育 概述 腾讯云智聆口语评测(英文版)(Smart Oral Evaluation-English,SOE-E)是腾讯云推出的语音评测产品,是基于英语口语类教育培训场景和腾讯云的语...

腾讯云加社区
今天
1
0
浅谈SpringMVC之DispatcherServlet

Spring的MVC框架是围绕一个DispatcherServlet其实就是个Servlet(它继承自HttpServlet基类)来设计的, 它支持可配置的处理器映射、视图渲染、本地化、时区与主题渲染、文件上传等 控制器一般...

恋码之子
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部