算法—贪心算法典型案例

大家好，欢迎来到IT知识分享网。

题目

下面考你一道算法题:有一个背包，容量是c;有若干物品，价值各不相同,重量也各不相同。接下来请你选择一部分物品装入背包，要保证不超过背包容量的前提下，背包中物品总价值最大。

思路

我的思路是这样的，供大家借鉴：我们已知每个背包的容量和价值，另外大背包的总容量也告诉我们了。

因为是可以将小包的一部分放入打包，那我们采用贪心算法

因为大背包的容量有限，我们可以先算出每个小背包的性价比，然后按照性价比的大小往依次背包里面放，直到放满为止，并在这个过程中求出大背包中物品的总价值。

代码

/** * treeMap通过key值进行升序排序 */
public class 部分背包问题11 { 
   
    //允许选择物品的一部分
    public static void main(String[] args) { 
   

        int[] value = { 
   9,3,1,6,5};
        int[] weight = { 
   4,6,3,2,5};
        //创建一个treeMap用来存储物品的价值，并且重写比较器的方法实现降序排序
        Map<Float,Integer> map = new TreeMap<Float,Integer>(new Comparator<Float>() { 
   
            @Override
            public int compare(Float o1, Float o2) { 
   
                return o2.compareTo(o1);
            }
        });

        int bbRongLiang = 10;
        int totalValue = 0;

        //将性价比添加到map集合并降序排序
        for (int i = 0; i < value.length; i++) { 
   
            float a = Float.valueOf(String.valueOf(value[i]));
            float b = Float.valueOf(String.valueOf(weight[i]));
            map.put(a/b,i);
        }
        //通过每个背包的性价比对应的背包号，来往背包里依次存放，直到背包满了为止，并计算出此时背包中的价值是多少
        for (int n : map.values()){ 
   
            if (bbRongLiang>=weight[n]){ 
   
                bbRongLiang = bbRongLiang - weight[n];
                totalValue = totalValue + value[n];
            }else { 
   
                //计算性价比,同时计算出最后一个包需要拿出多大的价值
                float someValue = (Float.valueOf(String.valueOf(bbRongLiang))/Float.valueOf(String.valueOf(weight[n]))) * value[n];
                String someValueStr = String.valueOf(someValue);
                String[] list = someValueStr.split("\\.");
                Integer someValueEnd = Integer.parseInt(list[0]);
                totalValue+=someValueEnd;
                break;
            }
        }
        System.out.println(totalValue);
    }
}