贪心算法(3)——最优装载、背包、乘船问题

1.最优装载

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

例1：【题目描述】有n个物体，第i个物体的重量为w_i（w_i为正整数）。选择尽量多的物体，使得总重量不超过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个物体的重量为w_i（w_i为正整数）。选择尽量多的物体，使得总重量不超过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个物体的重量为w_i，价值为v_i（w_i, v_i均为正整数）。在总重量不超过C的情况下让总价值尽量高。

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

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

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

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

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

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

物品	A	B	C	D	E	F	G
重量	35	30	60	50	40	10	25
价值	10	40	30	50	35	40	30
单位价值	0.28	1.3	0.5	1	0.87	4	1.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个人重量为w_i，每艘船的最大载重量为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;
}

---

返回目录：算法

---