贪心算法解决商场买赠问题（最简单，通俗易懂，附C++代码

设小明购买了n件商品，商品i的价格为Vi，1≤i≤n。现在商店推出打折服务，任意购买一件商品可赠送意见等值或更低价值商品。应如何选择付费商品和赠送商品的搭配才能使总付费额达到最小?自行编写程序，随机生成N件商品的基本数据，编程输出最小的付费金额和该方案的付费-赠送商品搭配。

贪心算法（greedy algorithm   ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解  。

1、首先是要先随机的生成N件商品以及其价格。

2、其次就是要对这些商品按照价格由大到小的顺序进行排序，因为要使得总付费金额最小而且还要能够选择赠送的商品，故而我们可以尝试买价格最高的选价格次高的，然后依次类推。

#include
#include
#include
const int N=10;
struct goods{
	int No;//商品编号
	int v;//价值
}; 
void selectsort(goods g[]){//选择排序 
	for(int i=0;i