当前位置：首页 > 算法 > 正文内容

【贪心】----最优装载、背包、乘船问题

亿万年的星光4年前 (2021-01-28)算法16698
1.最优装载

题目描述：有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。【分析】由于只关心选择的物品的最大数量（而不是最大重量，最大重量需要考虑DP），所以装重的物体没有装轻的物体划算。这里只需对n个物体按重量递增排序，依次选择每个物体直到装不下为止。这是一种典型的贪心算法，它只顾眼前，却能得到最优解。

例1：【题目描述】有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。
【输入描述】
n和C以及n个整数表示的wi。
【输出描述】
最后一行输出所选中的物体的个数num和总重量w,用空格分隔。
【样例输入】

10 100
20
20
5
25
28
10
3
4
8
9


【样例输出】

79  8

【参考代码】

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
int n,C;//n个物体 最大载重量C
int w[maxn]; //第i种物品的重量
int main() {
   int i;
   int ans=0,sum=0;//ans-选择的物品数 sum-当前物品总装量
   scanf("%d%d",&n,&C);
   for(i=0; i<n; i++)
       scanf("%d",&w[i]);
//按物品重量递增排序
   sort(w,w+n);
   for(i=0; i<n; i++) {
//如果能装载第i件物品，装载
       if(sum+w[i]<C) {
           sum+=w[i];
           ans++;
       }
   }
   printf("%d %d\n",sum,ans);
   return 0;
}


例2【题目描述】有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。
【输入描述】
n和C以及n个整数表示的wi。
【输出描述】
按照输入物体的顺序输出n个用空格分隔的Y或N。 Y表示该物体被选中，N表示不被选中。 最后一行输出所选中的物体的个数num和总重量w,用空格分隔。
【样例输入】

10 100
20
20
5
25
28
10
3
4
8
9


【样例输出】

Y Y Y N N Y Y Y Y Y
79 8
2.背包问题(01背包)


01背包：在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

比如： 有n个物体，第i个物体的重量为wi，价值为vi（wi, vi均为正整数）。在总重量不超过C的情况下让总价值尽量高。

比如下面这三个商品（重量限制是50）：



如果按照上述贪心算法按照重量来选择商品，那么选择的只有商品 1和商品2。他们的总价值量是160。但是这个题的组合还有商品1和商品3搭配价值量是180，上面2和商品3搭配，价值量是220。
在这几种选择情况中，我们前面的选择反而是带来价值最低的。而选择重量分别为20和30的物品带来了最大的价值。看来，我们刚才这种选择最佳的方式也行不通。

实际上，对于0-1背包问题，贪心选择之所以不能得到最优解，主要原因是：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。

3.背包问题(部分背包)

有n个物体，第i个物体的重量为wi，价值为vi（wi, vi均为正整数）。在总重量不超过C的情况下让总价值尽量高。每一个物体都可以只取走一部分，价值和重量按比例计算。

【分析】部分背包和01背包最大的区别就是部分背包可以只取走物品的一部分，也就是说可以随意切割。对于下面的例题（背包容量150）


物品ABCDEFG
重量35306050401025
价值10403050354030
单位价值0.281.30.510.8741.2


贪心策略可以有下面几种

  • 每次选取价值量最大的物品装入背包

  • 每次选取所占容量最小的物品装入背包

  • 每次选取单位价值量最大的物品装入背包

所以，按照第一种进行选取时 D F B E G（G取一部分）
重量：50 +10 +30 +40+20(G的一部分)=150
价值：50 + 40 + 40 +35+（30/25*20） = 189按照第二种进行选取时 F G B A E D(D取一部分)
重量：10+25+30+35+40+10 =150
价值：40+30+40+10+35+(50/50*10)=165按照第三种进行选取时 F B G D E(E一部分)
重量10+30+25+50+35=150
价值40+40+30+50+(35/40*35)=190.625

以上三种算法可以看出每次选取单位重量价值最大的是装入背包可以得出最优解。
所以，贪心算法解决部分背包按照重量和价值贪心是不对的。

4.最优装载—乘船问题

【题目描述】
有n个人，第i个人重量为wi，每艘船的最大载重量为C，且最多只能乘两个人。用最少的船装载所有人。题目保证有解。
【输入描述】
一共三行，第一行n表示有n个数，第二行输入n个数，第三行船的最大载重C
【输出描述】
一行，最少装载的船数。
【样例输入1】

6 
5 84 85 80 84 83
85


【样例输出1】

5


【样例输入2】

3
90 45 60
90


【样例输出2】

3


【分析】从最轻的人i开始考虑：如果每个人都无法和他一起坐船，则唯一的方法就是每人坐一艘船；否则，他应该选择能和他一起坐船的人中最重的一个j。这样的方法是贪心的，因为它只是让“眼前的浪费”最少。

        可以用反证法证明此策略的正确性：

        （1）i不与任何人同船。如果将j拉来与其同船，使用的船数<=原来的船数；

        （2）i与k同船。由贪心策略，因为此时i是最轻的，j是与i匹配的人中最重的，所以w[k]<=w[j]，则j加入其它船可能会使其它船超重，用的船数会变多；

        综上，说明这样的贪心法不会丢失最优解。

        故解题步骤：（循环过程）

        （1）将所有人的重量进行排序；

        （2）从当前最轻的人i开始考虑，找能跟其坐一艘船的最重的人j；

        （3）比最重的人j都重的人都单独坐一个船；

        需要特别注意的是：循环过程中若发现i=j，表明仅剩1人待安排，此时这个人自己一船。


参考代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1005;
int n,C;//n个人 船最大载重量C
int ans=0;//使用的最少船数
int w[maxn];//n个人的重量
int main() {
   int i,j;
   cin>>n;
   for(i=0; i<n; i++)
       cin>>w[i];
   cin>>C;
   sort(w,w+n); //预处理：n个人按重量递增排序
   i=0,j=n-1; //i.j分别用来标记待安排的最轻的人和最重的人
   while(i<=j) { //当还有人待安排时，循环
      //待安排的人中最轻的人和最重的人重量之和超过船的最大载重量
      //或者仅剩1人待安排时，j单独一船
       if(i!=j&& w[i]+w[j]>C) {
           ans++; //船数加1
           j--; //下一个最重的人
       }
      //其它情况：i和j两人同船
       else {
           ans++; //船数加1
           i++; //下一个最轻的人
           j--; //下一个最重的人
       }
   }
   cout<<ans<<endl;
   return 0;
}


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：【贪心】----找零钱问题

下一篇：【贪心】----排队打水

相关文章

【贪心】----基本概念

一、基本概念所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪...

【算法】前缀和与差分(2)一 一维数组差分

【算法】前缀和与差分(2)一 一维数组差分

一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。二、差分数组首先给定一个原数组a:   a[1]、a[2]、a[3]、......然后构造一个数组b: b[1]、b[2]、...

【排序】----冒泡排序

【排序】----冒泡排序

1.基本思想两个数比较大小，较大的数下沉，较小的数冒起来。2.过程·每次比较相邻的两个数，如果第二个数小，就交换位置。（升序或降序）·然后两两比较，一直到比较最后的数据。最终最小（大）数被交换到开始（...

【贪心】----找零钱问题

一、找零钱问题例题1：有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。X = 628最佳支付方法：3张200块的，1张20块的，1张5...

【算法】最短路径算法——Floyed-Warshell算法

【算法】最短路径算法——Floyed-Warshell算法

如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相怜。最短路径就是指连接两点的这些路径中最短的一条。【注意】边的权值可以为负。当出现负边权...

【算法】滑动窗口1—窗口大小固定

【算法】滑动窗口1—窗口大小固定

一、定义滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.