贪心——NYOJ题目106 背包问题

 

背包问题

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。

输出

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

样例输入

1
3 15
5 10
2 8
3 9

样例输出

65

分析：贪心原理，要求背包物品总价值最大，故尽可能多存放价值大的物品；如图 题目中给出的例子， 背包可容纳重量15，故先放价值最大的A，将10斤A全部放入背包，然后放入价值次大的C，此时背包容纳量剩下15-10=5，而C还有9斤，因此剩下的全放C，总价值=（10*5）+（5*3）=65

代码：

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct GOODS
{
	int v,w;//价值和重量都比较小<256 
}GOODS;

GOODS goods [10];

int cmp(const void * a,const void *b)
{
	return (*(GOODS *)a).v<  (*(GOODS *)b).v ? 1: -1;
}
int main()
{
	int s,n,m,i;
	int value,weight;
    scanf("%d",&n);
    while(n--)
    {
              scanf("%d%d",&s,&m);
              for(i=0;i<s;i++)     scanf("%d%d",&goods[i].v,&goods[i].w); 
			 qsort(goods,s,sizeof(goods[0]),cmp);  //将物品按价值从大到小排序 
			 //for(i=0;i<s;i++) printf("%d %d\n",goods[i].v,goods[i].w);
			 value = weight = i = 0;
			 
			 while(m)
			 {
					if(goods[i].w <= m)//这种物品的总质量 还小与目前背包容纳量，则全部装入 
					{
						m -= goods[i].w;
						value += goods[i].v *goods[i].w; //w重量的单价为v的物品价值 
					}
					else//将背包剩下的容量全部装这种物品 
					{
						value += goods[i].v * m; 
						m=0;
					} 
				
				i++;
			}   
			printf("%d\n",value);    
    }
  // system("pause");
 return 0;    
}