首页 > 上网技巧 > 电脑小技巧 > java实现贪心算法解决背包问题

java实现贪心算法解决背包问题

时间:2021-06-13 23:13 作者:QQ地带 我要评论

背包问题(贪心算法)
贪心算法思想
简单的说,就是将大问题转化为最优子问题,例如本题所要求的,背包容量有限,要想使物品的总价值最高,那么,我们必须尽可能的选择权重高的(即单位价值更高)的物品进行装载。
 
在背包问题中,物品是可拆的,即可以分成任意部分进行装载,而最终实现的目标是,背包是满的(即剩余容量为0),且总价值尽可能高。这也就是背包问题与0-1背包的根本差别所在。
 
解题思想
先将所有物品的权重进行排序(可以使用任何排序方法)
从权重最高的进行装载(如果装得下)
权重较高的装载成功后,包的最大剩余容量也随之变化,即减去上一物品的容量
继续重复2,3操作
直到最大剩余容量小于当前物品的重量,则将物品拆分成当前最大剩余容量
计算总价值以及各部分装载重量
代码如下:
 
public static void bG(Bag[] p,int k,int w,double v)
     {
    for(int i=k; i < p.length; i++){
         if(p[i].weight<=w)
         {
             v=v+p[i].value;
             System.out.println(p[i].pid+"全部装入,当前背包价值为"+v);
             w=w-p[i].weight;
         }else{
             double a=w*p[i].wi;//当前价值
             v=v+a;
             System.out.println(p[i].pid+"装入了"+((double)w/p[i].weight)+",当前背包价值为"+v);
         } 
         
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
完整代码实现如下
import java.util.Scanner;
 
 class Bag
 {
    public int weight;//重量
    public int value;//价值
    public double wi;//权重
    public String pid;//背包名称
    public  Bag(int w,int v,String pid)
    {
        this.weight=w;
        this.value=v;
        this.pid=pid;
        this.wi=(double)value/weight;
    }
 }
 
 public class bagGreed 
 {
     //选择排序将数组中的bag按权重排序(使用了选择排序)
     public static void sort(Bag[] p)
     {
         Bag t;
         for(int i=0;i<p.length;i++)
         {
             int max=i;
             t=p[i];
             for(int j=i;j<p.length;j++)
             {
                 if(t.wi<p[j].wi)
                 {
                     t=p[j];
                     max=j;
                 }
             }
             t=p[i];
             p[i]=p[max];
             p[max]=t;
             
         }
     }
     //算法核心
     public static void bG(Bag[] p,int k,int w,double v)
     {
    for(int i=k; i < p.length; i++){
         if(p[i].weight<=w)
         {
             v=v+p[i].value;
             System.out.println(p[i].pid+"全部装入,当前背包价值为"+v);
             w=w-p[i].weight;
         }else{
             double a=w*p[i].wi;//当前价值
             v=v+a;
             System.out.println(p[i].pid+"装入了"+((double)w/p[i].weight)+",当前背包价值为"+v);
         } 
         
    }
     }
     
     
     public static void main(String args[])
     {
         System.out.println("请输入背包的容量w和物品的个数n");
         Scanner reader = new Scanner(System.in);
         int w=reader.nextInt();//背包的容量
         int n=reader.nextInt();//物品的个数
         Bag[] p=new Bag[n];
         //10 10 a 10 10 b 10 15 c
         System.out.println("请依次输入各个物品的重量w和价值v和名称s");
         int weigth;
         int value;
         String pid;
         for(int i=0;i<n;i++)
         {
             weigth=reader.nextInt();
             value=reader.nextInt();
             pid=reader.next();
             p[i]=new Bag(weigth,value,pid);
         }
         sort(p);
         System.out.println("各物品的权重为:");
         for(int i=0;i<n;i++)
         {
             System.out.println(p[i].wi+" "+p[i].pid);
         }
         
         bG(p,0,w,0.0);
         
     }
 
 }
 

标签: java
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告