好贷网好贷款

贪婪算法---部分背包问题

发布时间:2016-12-3 6:14:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"贪婪算法---部分背包问题",主要涉及到贪婪算法---部分背包问题方面的内容,对于贪婪算法---部分背包问题感兴趣的同学可以参考一下。

贪心法的基本思路:——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 -------问题可以分解成子问题,子问题又可以继续分解成子问题.....,且具有最优结构性质. 该算法存在问题:1. 不能保证求得的最后解是最佳的;2. 不能用来求最大或最小解问题;3. 只能求满足某些约束条件的可行解的范围。 下面我重点介绍用贪婪算法解决部分背包问题,在解决部分背包问题时通常能得到最优解(我认为在贪婪算法中只要满足贪婪算法的基本条件外,如果每个问题的最优选择不会影响到子问题的解决的话及每个子问题都是相互独立的,那么这个问题用贪婪算法一般能得到最优解).实现该算法的过程:从问题的某一初始解出发;while 能朝给定总目标前进一步 do   求出可行解的一个解元素----一个问题的解元素(子问题的解元素);由所有解元素组合成问题的一个可行解;  下面举一个部分背包问题的例子: 有N个商品,每个商品的重量为WI,价格为:PI,现有一个背包,最多能装M的重量.其中(0<=I<N,0<wi<M). 问:怎样装能使包中装入的商品价值最高(对于每个商品可以只装该商品的一部分)? 下面是针对题目的程序.注:由于时间快我在程序中把每个商品都写到了程序中. package sf.tanxin; import java.util.*;class Ware{ public float weight;//商品开始的总重量 public float price;//商品完整时的价值 public float sweight;//当前商品的剩余重量 public int no;//商品编号 public Ware(float w,float p,float sw,int no){  this.weight=w;  this.price=p;  this.sweight=sw;  this.no=no;    }} class InWare{ public int no; public float weight;//该商品被装入部分的重量 public float price;//该商品被装入部分的价值 public InWare(int no,float w,float p){  this.no=no;  this.weight=w;  this.price=p;  } } public class BagProb{ private Ware[] ware=null; private List list=new ArrayList(); private float MaxWeInBag=0; private float MaxPriInBag=0;  public BagProb(Ware[] w,float maxW){  this.ware=w;  this.MaxWeInBag=maxW;  }    public void sortWare(){//利用商品的单位重量的价值来进行升序   int length=ware.length;   float tempWeight1,tempWeight2;   int flag=0;   for(int i=0;i<length-1;i++){    for(int j=0;j<length-i-1;j++){     tempWeight1=ware[j].price/ware[j].weight;     tempWeight2=ware[j+1].price/ware[j+1].weight;     if(tempWeight1<tempWeight2){      Ware temp=ware[j];      ware[j]=ware[j+1];      ware[j+1]=temp;      flag=1;      }     }     if(flag==0) break;        }   }      public List proceBag(){    sortWare();    int i=0;    float tempWei=ware[i].weight;    while(MaxWeInBag>=tempWei){     InWare inw=new InWare(ware[i].no,ware[i].weight,ware[i].price);     list.add(inw);     ware[i].sweight=0;     MaxWeInBag=MaxWeInBag-ware[i].weight;     i++;     tempWei=ware[i].weight;     }          if(MaxWeInBag>0){      float tempPrice=(MaxWeInBag/tempWei)*ware[i].price;      InWare inww=new InWare(ware[i].no,MaxWeInBag,tempPrice);      list.add(inww);      ware[i].sweight=ware[i].sweight-MaxWeInBag;      MaxWeInBag-=MaxWeInBag;      }               return list;      }          public void printInWare(){      int len=list.size();      InWare in=null;      int no;      float weight;      float price;      for(int i=0;i<len;i++){       in=(InWare)list.get(i);       no=in.no;       weight=in.weight;       price=in.price;       System.out.println("为达到最大价值,总共装入的商品如下:");       System.out.println("商品编号:"+no+" 装入重量为:"+weight+        "装入部分的价格为:"+price);       }      }            public static void main(String[] args){       Ware w1=new Ware(10,60,60,1);       Ware w2=new Ware(20,100,100,2);       Ware w3=new Ware(30,120,120,3);       Ware[] w={w1,w2,w3};       BagProb bgp=new BagProb(w,50);       bgp.proceBag();       bgp.printInWare();       }   } 以上是我对贪婪算法解决背包问题的认识,我知道我懂的很浅,文中也有我的个人观点,可能不正确,希望看到文章的高手门给予指正,也很希望和大家一起交流谈论.

上一篇:日记(4)耍酷与文静的结合
下一篇:从博德之门到形式语义

相关文章

相关评论