贪心——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;    
}