P2240 【深基12.例1】部分背包问题

题目大意
给定n个元素的基本信息，代价与价值，计算每个元素的性价比，使其和最大
显然，本题可以以贪心的思想去解决，每个元素可以分裂，因而不需要考虑全局最优解，所以可以贪心。其中，计算每个元素的性价比，即a.v / a.m > b.v / b.m，根据这个式子可变形得a.v * b.m > b.v * a.m，化除为乘，更加精确，根据性价比排序收集

#include <algorithm>
#include <iostream>
using namespace std;
struct coin
{
	int m;
	int v;
};
const int maxn = 100 + 5;
coin arr[maxn];
bool cmp(coin a,coin b)
{
	return a.v * b.m > b.v * a.m;
}
float ans = 0;
int main()
{
	int n,t;
	cin >> n >> t;
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i].m >> arr[i].v;
	}
	sort(arr,arr+n,cmp);
	int i;
	for(i = 0; i < n; i++)
	{
		if(t >= arr[i].m)
		{
			t -= arr[i].m;
			ans += arr[i].v;
		}
		else break;
	}
	if(i < n)ans += 1.0 * t / arr[i].m * arr[i].v;
	printf("%.2f\n",ans);
	return 0;
}

聊点闲话
贪心，更多的是一种思想，而并非一种算法，至于目光短浅，有时并非是一种坏事，有时，保持当前状态的最优解就能保证全局最优解，这就是贪心的思想，即局部最优。而贪心的正确性证明并不显然，只要举出反例，就能证明不可行。
证明贪心的合理性有以下几种方法
假设选择方案不是贪心要求的方案，证明贪心更好，至少不会更差
写一个暴力枚举搜索版本，答案一致，贪心很有可能是靠谱的
数学归纳法，步步最优，全局最优