题目 2041: 财富之沙(C语言代码)

解题思路:贪心算法

注意事项:需要把单价从大到小排序，重量也要相应地进行变换

参考代码:

#include<stdio.h>

int main(void)
{
	int n, m,temp,value=0;       //temp用作中间交换变量；value用于存储最大价值
	scanf("%d%d", &n, &m);
	int data[100000][2];            //存一组种类的沙子和重量
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &data[i][0], &data[i][1]);
	}
	for (int i = 0; i < n; i++)          //选择排序进行从大到小排序
	{
		for (int j = i + 1; j < n; j++)
		{
			if (data[i][0] < data[j][0])
			{
				temp = data[i][0];
				data[i][0] = data[j][0];
				data[j][0] = temp;
				temp = data[i][1];
				data[i][1] = data[j][1];
				data[j][1] = temp;
			}

		}
	}
	int i = 0;
	while (m)          //当剩余手套箱容量在全部装完某一种类沙子时正好装完，则m=0，退出循环
	{
		if (data[i][1] <= m)
		{
			value = data[i][0] * data[i][1] + value;
			m -= data[i][1];
			i++;
		}
		else
		{
			value = m * data[i][0] + value;        //剩余手套箱容量小于某一种类沙子的重量时，
			break;
		}
	}
	printf("%d\n", value);

	return 0;
}