精华内容
参与话题
问答
  • 背包算法

    2018-08-24 23:35:47
    背包:01背包、完全背包 01背包 假设有一个背包的负重最多可达8公斤,而希望在背包中装入负重范围内可得到的总价最多的物品,水果的编号、单价与重量如下所示: 种类 重量 价值 0 苹果 4 1 梨 ...

    背包:01背包、完全背包

    01背包

    假设有一个背包的负重最多可达8公斤,而希望在背包中装入负重范围内可得到的总价最多的物品,水果的编号、单价与重量如下所示:

    种类 重量 价值
    0 苹果 4
    1 5
    2 2
    3 香蕉 6
    4 橘子 1

    思想:

    动态规划,通过处理每个分阶段的最优结果,得到整个阶段的 最优结果。

    把水果装进背包,如果想装的总价值最高,那么就要保证背包的所有空间都是装载的最高的价值,(因为东西是一点一点装进去的,背包不是一次就被装满的,每装一次,就会有不一样的剩余空间的大小和当前背包中物品的总价值,所以就会有很多的子阶段的结果,形成一个集合,所以我们用数组来表示结果,f[w] 为背包容量为w时的最优解,也就是价值的最大值)

    <?php
    
    //把每种物品的重量和价钱存在两个数组中
    //分别为$weight , $value
    $weight=[4,5,2,1,6];
    $value=[4500,5700,2250,1100,6700];
    $bao=8;
    //用f 数组表示背包的总价格//初始化数组元素为0,当背包什么都没放的时候,总价格为0
    for($i=0;$i<=$bao;$i++)
    {
        $f[$i]=0;
    }
    //依次放水果
    for($i=0;$i<5;$i++)
    {
        for($j=$bao;$j>=$weight[$i];$j--)
    // j 为背包的空间,$j>=$weight[$i] 是为了使操作有效,背包空间大于物品质量的时候才能放,空间不够就不放,就看下一个 $i++;
    //i 为 0 时重量为4,那么当背包容量只剩下3时就不走了
        {
            //可以放,那就判断当下情况是放了之后价值高还是不放高,取其中最大值,作为当前背包容量为 j 的时候背包中最高的价值;(比较的时候注意放了之后的价值,是在背包总重量去除放的物品的重量的时候,剩余的容量能够放的最高的价值加上新放的物品的价值)
            $f[$j]=max($f[$j],$f[$j-$weight[$i]]+$value[$i]);
            //var_dump($i);
            //var_dump($j);
            //var_dump($f[$j]);
            //var_dump($f);
            //echo '<hr>';
            //去做 $j-- ,要一直处理,得到背包在各种剩余容量的时候的最大价值,
        }
    }
    var_dump($f[$bao]);//背包容量为 $bao 时的最大价值

    每阶段结果

    放入第二个的时候,会判断背包的每个子阶段在能放的情况下是否产生了新的最大值,并刷新子阶段的结果,作为新的每个阶段的最优解, (f[j]=max(f[j],f[j-weight[i]]+value[i]);)
    如果我要想往里放,是不是得考虑在背包腾出这么大的地方后,我把它放进去是比之前的值大的
    依次判断刷新,求出最优解 9095

    完全背包

    完全背包解决的是每种物品不限量的情况,能拿多少拿多少

    二者区别在于01背包是装一个就走,完全背包是能装就装

    01背包:for(j=bao;j>=weight[i];j–)

    完全背包:for(j=weight[i];j<=bao;j++)

    01背包从背包最大容量开始操作,因为容量递减,而且每次都是和小容量比较来得出大容量的价值,当装一种物品时,从最大的那个子阶段刷新值,先更新的大的,所以大的阶段的值没机会再根据子阶段后续的变化而得到最新的值,(也就是无论背包的容量有多大,对于一类物品 i,都只能装一个)

    完全背包在背包容量满足装载的最小值开始,也就是 j=weight[$i],先处理小的子阶段,导致在之后处理的更大的子阶段的时候值能够得到更新,也就是装了一个物品i之后,

    还能在以后 $j++ 满足情况的时候继续装多个物品i。实现了能装多少装多少

    <?php
    
    $weight=[4,5,2,1,6];
    $value=[5500,5700,2250,1100,6700];
    $bao=8;
    
    for($i=0;$i<=$bao;$i++)
    {
        $f[$i]=0;
    }
    
    for($i=0;$i<5;$i++)
    {
        for($j=$weight[$i];$j<=$bao;$j++)
        {
            $f[$j]=max($f[$j],$f[$j-$weight[$i]]+$value[$i]);
            //var_dump($i);
            //var_dump($j);
            //var_dump($f[$j]);
            //var_dump($f);
            //echo '<hr>';
        }
    }
    var_dump($f[$bao]);
    展开全文
  • 因为只要懂动态规划就可以很轻松搞定0-1背包算法(部分背包算法更简单,排序即可)。之前看了很多篇文章都觉得太难了,好复杂,其实只是每个人逻辑思维不一样,别人说的你不一定能理解,但是多看几篇文章,总有一片...

    这篇文章过程讲得很详细,一文搞懂(点击看原文)

    不懂之前觉得很难理解,觉得很复杂,其实没有必要。因为只要懂动态规划就可以很轻松搞定0-1背包算法(部分背包算法更简单,排序即可)。之前看了很多篇文章都觉得太难了,好复杂,其实只是每个人逻辑思维不一样,别人说的你不一定能理解,但是多看几篇文章,总有一片你能轻易理解(就像上面那篇,一看懂)。

    进入正题,由于上面的文章讲得很详细了,建议大家都去看上面的文章,这篇文章主要是给大家打个预防针,不要觉得很复杂(至少我一开始就觉得很复杂,过程各种疑问),搞懂了才发现,简单到爆炸。以及后面给出优化的思路(原文没有写的)

     

    首先搞懂什么是背包算法

    背包算法可以理解为在解题的过程中,模拟一个背包(二维数组),来记录背包从小到大的过程中能装的最有价值的东西,并且大多数题目都是以装东西为题,所以大家叫背包算法也很合理

    01-背包算法和部分背包算法

    0-1背包算法就是一个物品要么拿或者不拿,就像音响、吉他这样的物品。部分背包算法则是每个物品可以拿一部分,不需要全部拿完,像装沙子(10kg,60)、装水(20kg,100)、装饼干(30kg,120),数量各不一样,价值各不一样,怎么拿才能拿价值最高呢?(肯定全部拿最贵的啊。。。)

    所以两种算法,较为复杂的是0-1背包算法(动态规划),部分背包算法很简单:如上面的沙子、水、和饼干,1kg沙子价值6,1kg水价值5,1kg饼干价值4,所以当一个50kg的背包,最划算的拿法肯定是先拿沙子(最贵,能拿完就拿完),同理,拿完水,最后还剩20kg的容量,拿饼干。

    部分背包算法,就跟上面一样,很简单

    接下来看一下0-1背包算法,动态规划的思想

    采用从左到右(背包从1到最大容量),加上从上到下(可选择的物品从1个到n个)的双动态规划

    具体的演示过程,上面文章写的很详细,我就不演示了。

    对于一个物品(w=5,v=10),其在背包容量为n的时候,他有两者选择,拿这个物品,不拿这个物品

    拿,    则价值=该物品价值v+背包容量【当前容量n-物品容量w】能装的最大价值  (动态规划,而不需要去重新排列组合计算)

    不拿,则价值=背包容量【n】能装的最大价值(除了自己)。(也是动态规划,从上到下(物品从1件到n件))

    所以比较拿与不拿就可以得出该容量的背包,该物品该不该拿

    如果没看懂,可以去看原文的图解过程,真的和容易理解

    这篇文章就是想大概给大家个方向,然后大家去看详细的图解过程绝对可以一看就懂

    时间复杂度O(n*c) 空间复杂度O(n*c)

    n为物品种类,c为规定的背包大小

    优化思路

    从图解可以看出,二维数组其实只会用到上一行的数据,即当行数为3时,只会通过第二行的数据来动态规划即可

    所以n行的二位数组可以改成2行(一行记录上一行,一行记录当前行,需要多花n*c次遍历的时间,时间换空间的取舍)

    递归思想

    图解的过程是从上到下,从左到右,递归则可以相反,从最右边和最下边开始递归

    即直接计算需要的答案   result=array[n][c]

    计算array[n][c]的时候需要递归的去计算array[n-1][c]和array[n-1][c-w]+v的值做比较

    通过这样逆序的去计算,最终也能得到结果,时间复杂度也是O(n*c),空间复杂度可以为O(1)

    以上纯属个人总结,如果不对请指出,谢谢,更详细的题解可以看原文,图解过程很详细了

     

     

     

     

     

    展开全文
  • java背包算法例子

    2010-02-26 11:35:30
    原先在网上找到某位大虾写的一个简单的背包算法,于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合(其中的对象中只包含主键和值)和某个条件值,然后能打印sum(对象.值)条件的1个...
  • 背包算法设计

    2013-06-04 12:25:44
    背包算法的设计代码,很不错的,计算机算法设计
  • 超递增背包算法

    2017-09-11 11:06:27
    密码学超递增背包算法,十分简单实用,过程详细,注释清晰,结构严谨,比较适合初学者进行学习。帮助多多哦
  • Java背包算法规划求解

    2017-02-13 10:13:24
    背包算法规划求解,解决问题场景如:售货架中有n种商品(每种商品只有一个),给定200块钱购物,尽可能的购买到更多的商品,将这本金最大化利用。
  • 各种背包算法详解

    2012-10-30 19:24:18
    对各种背包问题的详解,01背包,多重背包等等
  • 经典算法详解 之 背包算法

    万次阅读 多人点赞 2012-04-23 00:12:30
    背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。这个问题涉及到了两个条件:一...

              背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。这个问题涉及到了两个条件:一是物品总的大小小于或等于背包的大小,二是物品总的价值要尽量大。

    如果我们用子问题定义状态来描述的话可以这样解释

    f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。用公式表示:


                           f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} f[v]=max{f[v],f[v-c[i]]+w[i]}


        具体的解释可以理解为将前i件物品放入容量为v的背包中,只考虑第i件物品的策略(放或不放),那么就可以转化为一个只涉及前i-1件物品和第i件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。v表示背包的最大容量,c[i]表示第i件物品的大小,w[i]表示第i件物品的价值)


    算法如下:

    class Fruit{
    	private String name;
    	private int size;
    	private int price;
    	
    	public Fruit(String name,int size,int price){
    		this.name=name;
    		this.size=size;
    		this.price=price;
    	}
    	public String getName(){
    		return name;
    	}
    	public int getPrice(){
    		return price;
    	}
    	public int getSize(){
    		return size;
    	}
    }
    
    public class Knapsack{
    	public static void main(String[] args){
    		final int MAX=8;
    		final int MIN=1;
    		int[] item=new int[MAX+1];
    		int[] value=new int[MAX+1];
    		Fruit fruits[]={
    			new Fruit("李子",4,4500),
    			new Fruit("苹果",5,5700),
    			new Fruit("橘子",2,2250),
    			new Fruit("草莓",1,1100),
    			new Fruit("甜瓜",6,6700)
    		};
    		for(int i=0;i<fruits.length;i++){
    			for(int s=fruits[i].getSize();s<=MAX;s++){//s表示现在背包的大小
    				int p=s-fruits[i].getSize();//表示每次增加单位背包空间,背包所剩的空间
    				int newvalue=value[p]+fruits[i].getPrice();//value[p]表示增加的背包空间可以增加的价值,fruits[i].getprice()表示原有的背包的价值
    				if(newvalue>value[s]){//现有的价值是否大于背包为s时的价值
    					value[s]=newvalue;
    					item[s]=i;//将当前的水果项添加到背包的物品中
    				}
    			}
    		}
    		System.out.println("物品\t价格");
    		for(int i=MAX;i>MIN;i=i-fruits[item[i]].getSize()){
    			System.out.println(fruits[item[i]].getName()+
    				"\t"+fruits[item[i]].getPrice());
    		}
    		System.out.println("合计\t"+value[MAX]);
    	}
    }

    程序运行的过程如下:

     

    i=0时放入李子

    背包负重

    1

    2

    3

    4

    5

    6

    7

    8

    s

    4

    5

    6

    7

    8

    p

    0

    1

    2

    3

    4

    value

    0

    0

    0

    4500

    4500

    4500

    4500

    9000

    item

    0

    0

    0

    0

    0

    i=1时放入苹果

    背包负重

    1

    2

    3

    4

    5

    6

    7

    8

    s

    5

    6

    7

    8

    p

    0

    1

    2

    3

    value

    0

    0

    0

    4500

    5700

    5700

    5700

    9000

    item

    0

    1

    1

    1

    0

    i=2放入橘子

    背包负重

    1

    2

    3

    4

    5

    6

    7

    8

    s

    2

    3

    4

    5

    6

    7

    8

    p

    0

    1

    2

    3

    4

    5

    6

    value

    0

    2250

    2250

    4500

    5700

    6750

    7950

    9000

    item

    2

    2

    0

    1

    2

    2

    0

    i=3放入草莓

    背包负重

    1

    2

    3

    4

    5

    6

    7

    8

    s

    1

    2

    3

    4

    5

    6

    7

    8

    p

    0

    1

    2

    3

    4

    5

    6

    7

    value

    1100

    2250

    3350

    4500

    5700

    6800

    7950

    9050

    item

    3

    2

    3

    0

    1

    3

    2

    3

    i=4放入甜瓜

    背包负重

    1

    2

    3

    4

    5

    6

    7

    8

    s

    6

    7

    8

    p

    0

    1

    2

    value

    1100

    2250

    3350

    4500

    5700

    6800

    7950

    9050

    item

    3

    2

    3

    0

    1

    3

    2

    3

     

        由最后一个表格可以知道,在背包负重8的时候,最多得到价值9050的水果,这个时候可以得到装入的水果是3号水果草莓,那么剩下的(8-1=7)个大小空间,可以知到为2号水果也就是橘子,同理下一步可以知道放入的水果是1号水果苹果。此时获得的最优解的价值就是9050,放入的水果是草莓、橘子和苹果。

        到此,我们的背包问题已经解决,要了解上述算法,需要读者分析出背包算法中的每一步都做了什么操作,这一点可以通过上述的表格看出,希望本文对读者理解背包算法有所帮助!


    展开全文
  • 01背包算法 C语言代码

    2011-10-26 14:49:29
    01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码
  • C语言算法之背包算法

    2013-09-29 19:52:02
    在0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi .对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品...
    
    

    0 / 1背包问题中,需对容量为的背包进行装载。从个物品中选取装入背包的物品,每件物品的重量为wi ,价值为pi .对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即i=1pi xi 取得最大值。约束条件为i =1wi xi≤c xi[ 0  1 ]  1≤i≤n)。

        在这个表达式中,需求出xt 的值。xi = 1表示物品装入背包中,xi =0 表示物品不装入背包。0 / 1背包问题是一个一般化的货箱装载问题,即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为:船作为背包,货箱作为可装入背包的物品。 1-8 在杂货店比赛中你获得了第一名,奖品是一车免费杂货。店中有种不同的货物。规则规定从每种货物中最多只能拿一件,车子的容量为c,物品需占用wi 的空间,价值为pi .你的目标是使车中装载的物品价值最大。当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模,其中车对应于背包,货物对应于物品。

        0 / 1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,考虑n=2 w=[1001010] p =[201515] c = 1 0 5.当利用价值贪婪准则时,获得的解为x= [ 1  0  0 ],这种方案的总价值为2 0.而最优解为[ 0  1 ],其总价值为3 0.

        另一种方案是重量贪婪准则是:从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。考虑n= 2 w=[1020] p=[5100] c= 2 5.当利用重量贪婪策略时,获得的解为x =[10] 比最优解[ 0  1 ]要差。

        还可以利用另一方案,价值密度pi /wi 贪婪算法,这种选择准则为:从剩余物品中选择可装入包的pi /wi 值最大的物品,这种策略也不能保证得到最优解。利用此策略试解n= 3 w=[201515] p=[402525] c=30 时的最优解。

        我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧, 0 / 1背包问题是一个N P-复杂问题。对于这类问题,也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递(增)减的次序装入物品不能保证得到最优解,但它是一个直觉上近似的解。我们希望它是一个好的启发式算法,且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中,用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %,所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在nl o gn)时间内获得如此好的性能。我们也许会问,是否存在一个x<1 0 0 ),使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点,考虑例子n =2 w = [ 1 y] p= [ 1 0  9y] c= y.贪婪算法结果为x=[10] 这种方案的值为1 0.对于y≥1 0 / 9,最优解的值为9 y.因此,贪婪算法的值与最优解的差对最优解的比例为(  9y - 1 0/9y* 1 0 0  %,对于大的y,这个值趋近于1 0 0 %.但是可以建立贪婪启发式方法来提供解,使解的结果与最优解的值之差在最优值的x% x<100 之内。首先将最多件物品放入背包,如果这件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为件物品的所有可能的子集来得到最优解。

        13-9 考虑n =4 w=[2467] p=[6101213] c = 11.k= 0时,背包按物品价值密度非递减顺序装入,首先将物品1放入背包,然后是物品2,背包剩下的容量为5个单元,剩下的物品没有一个合适的,因此解为x = [ 1  1  0  0 ].此解获得的价值为1 6.

        现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 }  { 2 }  { 3 }  { 4 }.子集{ 1 }  { 2 }产生与k= 0时相同的结果,考虑子集{ 3 },置x3 1.此时还剩5个单位的容量,按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1,它适合,因此取x1 1,这时仅剩下3个单位容量了,且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1  0  1  0 ],获得的价值为1 8.若从子集{ 4 }开始,产生的解为x = [ 1  0  0  1 ],获得的价值为1 9.考虑子集大小为01时获得的最优解为[ 1  0  0  1 ].这个解是通过k= 1的贪婪启发式算法得到的。

        k= 2,除了考虑k< 2的子集,还必需考虑子集{ 1  2 }  { 1  3 }  { 1  4 }  { 2  3 }  { 2  4 }{ 3  4 }.首先从最后一个子集开始,它是不可行的,故将其抛弃,剩下的子集经求解分别得到如下结果:[ 1  1  0  0 ]  [ 1  0  1  0 ]  [ 1  0  0  1 ]  [ 0  1  1  0 ][ 0  1  0  1 ],这些结果中最后一个价值为2 3,它的值比k= 0k= 1时获得的解要高,这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法(k - o p t i m a l)。也就是,若从答案中取出件物品,并放入另外件,获得的结果不会比原来的好,而且用这种方式获得的值在最优值的( 1 0 0 / k + 1   %以内。当k= 1时,保证最终结果在最佳值的5 0 %以内;当k= 2时,则在3 3 . 3 3 %以内等等,这种启发式方法的执行时间随的增大而增加,需要测试的子集数目为nk ),每一个子集所需时间为n),因此当k >0时总的时间开销为nk+1 )。实际观察到的性能要好得多。


    展开全文
  • 公钥算法之背包算法

    2011-08-08 10:22:00
    这是一个非对称算法,即可生成多个不同的公钥,分发给其他...1.背包算法基于背包问题的简化版,即子集和问题(Subset sum)。 2.子集和问题:给定一个整数集A(俗称为背包)和整数b,要求找出A的一个子集,使得其中...
  • C# 背包算法

    千次阅读 2018-11-20 22:19:39
    原文: https://www.jb51.net/article/64540.htm using System; namespace BackRack { //要装入书包的货物节点 class BagNode { public int mark;//货物编号,从0开始记 public int weight;... ...
  • 本篇文章主要介绍了浅谈java实现背包算法(0-1背包问题) ,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

空空如也

1 2 3 4 5 ... 20
收藏数 7,389
精华内容 2,955
关键字:

背包算法