本文共 2172 字，大约阅读时间需要 7 分钟。

贪心算法，先按照单价从小到大排序，然后按照单价从最便宜的开始买，直到钱用完为止。

package 培训;import java.util.Scanner;//贪心public class 老鼠换猫粮 {	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		while (true) {			int maoliang = sc.nextInt();			if (maoliang == -1)				return;			int n = sc.nextInt();			MyData[] array = new MyData[n];			// 输入具体数据并计算单价信息			for (int i = 0; i < array.length; i++) {				array[i] = new MyData();				array[i].food = sc.nextInt();				array[i].price = sc.nextInt();				array[i].priceA = array[i].price / array[i].food;				array[i].priceB = array[i].food / array[i].price;			}			fun(maoliang, array);		}	}	// array=磅数 价格	static void fun(double maoliang, MyData[] array) {		double sumFood = 0; // 总共买的粮食		// MyData[] sortArray = new MyData[array.length];		// 按照单价排序		MyData temp = null;		for (int i = 1; i < array.length; i++) {			for (int j = 0; j < array.length - i; j++) {				if (array[j + 1].priceA < array[j].priceA) {					temp = array[j];					array[j] = array[j + 1];					array[j + 1] = temp;				}			}		}		int buyIndex = 0; // 当前买到第几个		while (maoliang > 0) {			// 钱太多 粮食不够			if (maoliang * array[buyIndex].priceB > array[buyIndex].food) {				// 这一组全买了				maoliang = maoliang - array[buyIndex].food						* array[buyIndex].priceA;				sumFood += array[buyIndex].food;				array[buyIndex].food = 0;				buyIndex++;			} else {				sumFood += array[buyIndex].priceB * maoliang;				array[buyIndex].food -= array[buyIndex].priceB * maoliang;				maoliang = 0;			}		}		System.out.printf("%.3f\n", sumFood);	}	static class MyData {		double food; // 剩余磅数		double price; // 价格		double priceA; // 一磅多少钱		double priceB; // 一块钱多少磅	}}

转载地址：http://yryvb.baihongyu.com/