贪心算法(二)——一般背包问题

题目

有一个背包,最多放M kg的物体(物体大小不限); 有n个物体,每个物体的重量为Wi,每个物体完全放入背包后可获得收益Pi。问:如何放置能获得最大的收益?

注:背包问题分为两种,若每个物体不可分割,则称为0/1背包问题,这种问题无法用贪心法求的最优解,只能求的近似解。而若每个物体可以切分,则称为一般背包问题,可以使用贪心法求的最优解。下面讨论的就是一般背包问题。

结果集

一般背包问题中,结果集可以用一个n元组表示: 1. x的下标i表示物体的序号; 2. xi表示第i个物体加入背包的部分(0<=xi<=1)

目标函数

使用贪心法解决最优化问题的第一步,就是要从题目中抽象出目标函数,这是一个数学建模的过程。 本题中,目标函数就是当前背包收益的最大值:

约束条件

所选的物体放入背包后,不能超过背包载重M:

最优量度准则1:重量小的物体优先

将所有物体按照重量递增的顺序排序,每次选重量最小的放入背包。

这个最优量度标准显然无法得到整体最优解,因为重量小的物体并不一定价值高。最优解与价值、重量这两个维度产生关系,而这个最优量度标准仅考虑了一个维度,因此这样选择并不能导致整体最优解。

最优量度准则2:价值高的物体优先

这种选法也无法达到整体最优解,理由同上。

最优量度准则3:性价比高的物体优先

首先计算所有物体的性价比(重量和收益的比值),每次优先将性价比高的物体放入背包。

代码实现

/**
 * 定义一个物体类
 */
class Body{
   int id;// 物体的序号
   int w;// 物体的重量
   int p;// 物体的价值
}
/**
 * 一般背包问题的代码实现
 * @param w:每个物体重量的数组
 * @param p:每个物体收益的数组
 * @param m:背包载重
 * @return 结果集(放入哪几个物体、每个物体放入多少部分)
 */
List<Body> commonPackage( int[] w, int[] p, int m ){
    // 构造物体对象列表(将入参存储在List<Body>中)
    List<Body> bodys = new ArrayList<>();
    for ( int i=0; i<w.length; i++ ) {
        bodys.add(new Body(w[i],p[i]));
    }
    // 对性价比排序(从高到低排序)
    Collections.sort(bodys, new Comaprator<Body>(){
        int compare(Body b1,Body b2){
            return b2.p/b2.w-b1.p/b1.w;
        }
    });
    // 将物体按照性价比从高到低依次加入背包
    int rest = m;// 剩余重量
    int i=0;
    List<Body> results = new ArrayList<>();// 存放结果集
    for(; i<bodys.size(); i++){
        if ( rest<bodys.get(i).w )
            break;
        Body curBody = bodys.get(i);
        results.add(curBody);
        rest -= curBody.w;
    }
    // 计算最后一个物体能放入的部分
    Body lastBody = bodys.get(i);
    results.add(new Body(lastBody.id,rest,(lastBody.p*rest/lastBody.w));
}

总结

要用贪心法解决一个最优化问题,首先要抽象出目标函数、约束条件,再判断结果能否用一个n元组表示。最后选择最优量度标准。 最优量度标准的选择有多种方式,并不是所有的最优量度标准都能导致整体最优解。最优量度标准的选择往往是先根据经验,然后再通过数学归纳法的方式证明它能导致整体最优解。 若无法选出一个最优量度标准,则可以使用动态规划法解决最优化问题。

补充:Java Collections.sort的使用

  1. 使用对象默认的排序规则
 List<String> list = new ArrayList<>(); Collections.sort(list);

如果没有在sort函数中指定具体的排序规则,则容器会使用容器中存储对象内部的compareTo函数进行排序。由于String类已经重写了compareTo函数,因此这时就会根据这个compareTo进行排序。如果对象没有重写compareTo函数,则默认使用从Object继承的compareTo函数,这就会根据地址的哈希值进行排序。

  1. 在对象中自定义排序规则
List<Person> list = new ArrayList<>();
Collections.sort(list);

class Person implements Comparable<Person>{
    ……
    @Override  
    public int compareTo(Person p) {  
        return this.name.compareTo(p.getName());
    }  

}
  • 容器中存储的对象类需要实现Comparable接口,并覆盖其中的compareTo函数;
  • 该函数的参数只有一个。
  1. 在sort函数中传入自定义排序规则
List<Person> list = new ArrayList<>();
Collections.sort(list,new Comparetor<Person>{
    public int compare(Person p1, Person p2){
        return p1.getName().compareTo(p2.getName());
    }
});
  • 创建一个Comparetor子类对象,并覆盖compare函数;
  • 该函数有两个参数!
  • 由于Object中的compareTo函数是public,因此可以在compare函数、compareTo中直接调用对象某一属性的compareTo函数进行比较。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java开发者杂谈

算法之数组和问题

算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

3658
来自专栏微信公众号:Java团长

十大经典排序算法最强总结(含Java代码实现)

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位...

871
来自专栏ACM算法日常

一次看懂进制转换(阶乘是关键) - HDU 2031

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

1133
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

3267
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

1002
来自专栏钱塘大数据

【推荐收藏】十大经典排序算法(动图演示)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

682
来自专栏ACM算法日常

基础算法|4 简单选择排序

我们之前已经了解了三种基础算法,分别为二分查找算法,冒泡排序算法,以及直接插入排序算法。俗话说得好,温故而知新,所以现在就让我们简单回顾一下之前的三种算法吧。...

1033
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

3729
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1204
来自专栏目标检测和深度学习

常用排序算法总结(1)

1062

扫码关注云+社区