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

傷城~ 2022-08-20 07:25 186阅读 0赞

思路: 首先将物品根据性价比排好序在一个集合里,性价比=价格/重量...

然后根据性价比从大到小依次依次放入背包,如果没办法放入这个物品的全部,就放入一部分,如果可以放入全量物品,就放入全量物品。

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;
        }
    
    }