文档章节

完全背包

曾劲松
 曾劲松
发布于 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
武汉

暂无文章

咕泡-Factory设计模式笔记

个人感悟: 设计模式都是处理复杂问题的,如果问题本身很简单,使用设计模式反而累赘,增加了开发的复杂性 遇到最简单的情况,直接 new 如果创建对象的过程简单,但是需要匹配不同情况,返回...

职业搬砖20年
19分钟前
0
0
Java中的锁分类

在读很多并发文章中,会提及各种各样锁如公平锁,乐观锁等等,这篇文章介绍各种锁的分类。介绍的内容如下: 公平锁/非公平锁 可重入锁 独享锁/共享锁 互斥锁/读写锁 乐观锁/悲观锁 分段锁 偏...

Funcy1122
27分钟前
0
0
Ansible随机数

想为你的Ansible剧本取一个随机数?还想在接下来的运行中保持系统的等幂性?这里有一个答案。 假如,你要为一大批服务器设置cron任务,却不想让它们同时启动,你可以这样设置分钟数: minute...

大别阿郎
36分钟前
0
0
SpringCloud之服务注册中心Eureka

本系列介绍的配置均基于 Spring Boot 2.0.1.RELEASE 版本和 Spring Cloud Finchley.SR1 服务注册中心 Spring Cloud 已经帮我们实现了服务注册中心,我们只需要很简单的几个步骤就可以完成。 ...

熊小飞呀
今天
9
1
“Comparison method violates ...”异常的再现方法

前提条件:JDK8 代码: import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Test { public stat......

hunterli
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部