P2240部分背包问题(贪心法)

P2240部分背包问题

题目选自洛谷

P2240部分背包问题(贪心法)
题目思路:用结构体存储金币总量和价值用排序优先拿走单位价格大的金币。代码附下:

#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;

struct node
{
	int m;
	int v;
	double dw;
}pp[105];

int cmp(node pp,node b)
{
	return pp.dw>b.dw;
}

int main()
{
	int n,t,z=0;
	double v1=0;
	cin>>n>>t;
	for(int i=0;i<n;i++)
	{
		cin>>pp[i].m>>pp[i].v;
		pp[i].dw=(double)pp[i].v/pp[i].m;
	}
	sort(pp,pp+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(t-pp[i].m>=0)
		{
			t-=pp[i].m;
			v1+=pp[i].v;
			z++;
		}else
		{
			v1+=(pp[z].dw*t);
			break;
		}
			
	}
	printf("%.2lf",v1);
	return 0;
 } 
上一篇:autojs教程:成语红包群app自动脚本代码


下一篇:面向对象的多态性和方法的重写与重载