首页 > 上网技巧 > 电脑小技巧 > Java描述贪心算法解决背包问题

Java描述贪心算法解决背包问题

时间:2021-06-06 22:58 作者:QQ地带 我要评论

思路: 首先将物品根据性价比排好序在一个集合里,性价比=价格/重量...
 
然后根据性价比从大到小依次依次放入背包,如果没办法放入这个物品的全部,就放入一部分,如果可以放入全量物品,就放入全量物品。
 
 
 
Main.java的代码
 
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
/**
 * Created by HuLuo on 2016/2/16.
 */
public class Main
{
    //背包总质量
    private static double M = 20;
 
    //物品数量
    private static int number = 3;
 
 
    public static void main(String[] args)
    {
        MyObject myObject1 = new MyObject( 18, 25 );
 
        MyObject myObject2 = new MyObject( 15, 24 );
 
        MyObject myObject3 = new MyObject( 10, 15 );
 
        ArrayList<MyObject> myObjects = new ArrayList<MyObject>( number );
 
        myObject1.priceRatio = ( myObject1.price * 1.0 ) / ( myObject1.weight );
 
        myObject2.priceRatio = ( myObject2.price * 1.0 ) / ( myObject2.weight );
 
        myObject3.priceRatio = ( myObject3.price * 1.0 ) / ( myObject3.weight );
 
 
        myObjects.add( myObject1 );
        myObjects.add( myObject2 );
        myObjects.add( myObject3 );
 
 
        //根据物品的性价比将集合中的物品做一个排序 ,按照性价比从大到小排列
        Collections.sort( myObjects, new Comparator<MyObject>()
        {
            @Override
            public int compare(MyObject o1, MyObject o2)
            {
                if(o1.priceRatio > o2.priceRatio)
                {
                    return -1;
                }
                else
                    return 1;
            }
 
        } );
 
        MyObject temp = null;
 
        for(int i = 0; i < number && M > 0; i++)
        {
            temp = myObjects.get( i );
 
            if(M >= temp.weight)
            {
                M = M - temp.weight;
 
                temp.x = 1.0;
            }
 
            else
            {
                temp.x = ( M * 1.0 ) / temp.weight;
 
                M = M - ( temp.weight * temp.x );
            }
        }
 
        for(MyObject myObject : myObjects)
        {
            System.out.println( "物品价格是:" + myObject.price + "的物品, 装入比例是:" + myObject.x );
        }
 
    }
}
 
 
 
 
MyObject.java文件的代码
 
/**
 * Created by HuLuo on 2016/2/16.
 */
 
/**
 * 物品对象
 */
public class MyObject
{
 
    public int weight = 0;
 
    public int price = 0;
 
    //装入的比例
    public double x = 0;
 
    //性价比
    public double priceRatio = 0 ;
 
    public MyObject(int weight, int price)
    {
        this.weight = weight;
 
        this.price = price;
    }
 
}

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

Google提供的广告