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

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

亿万年的星光4年前 (2021-01-28)算法15929
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;
}


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

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

分享给朋友：
返回列表

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

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

相关文章

【算法】高精度（1）

一、  什么是高精度高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算...

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

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

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

【算法】动态规划（二）——数字三角形问题

【算法】动态规划（二）——数字三角形问题

1.问题描述及状态定义数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：从第一行开的数开始走，每次可以往下或右走一格，直到走到...

【算法】归并排序

【算法】归并排序

【参考代码】void msort(int s, int t){ if(s==t) return ;  //如果只有一...

【贪心】最大子矩阵

【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1X1)子矩阵。比如,如下4 x 4的矩阵0    -2&...

【贪心】 导弹拦截

【贪心】 导弹拦截

【题目描述】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.