贪心法卖月饼

Posted on | In | Visitors:

问题描述

现有三种月饼，其库存量分别为 18、15、10 万吨，每种月饼总售价分别为 75、72、45亿元。如果市场的最大需求量只有 20 万吨，那么卖这三种月饼的最大收益是多少？（销售时允许取出一部分库存）

输入：

每次输入给出月饼种类数、以万吨为单位的市场最大需求量、各种月饼的总售价，以及各种月饼的库存量。

输出：

给出最大收益

思路

因为允许销售时只取出某种月饼的一部分库存，显然属于部分背包问题，可以用贪心法求最优解。计算每种月饼的单价，将其降序排列，再由高至低依次选择，直至满足需求量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.Scanner;
public class MoonCake {
    public static void main(String[] args){
        Scanner In = new Scanner(System.in);
        System.out.println("月饼的种类数：");
        int n = In.nextInt();
        double[] stock = new double[n]; //月饼库存数组stock
        double[] price = new double[n]; // 月饼总售价数组price
        System.out.println("各种月饼的库存量：");
        for(int i=0; i<n; i++) {
            stock[i] = In.nextInt();
        }
        System.out.println("各种月饼的总售价：");
        for(int j=0; j<n; j++) {
            price[j] = In.nextInt();
        }
        System.out.println("月饼的总需求量：");
        double c = In.nextInt();
        int[] index = new int[n];
        In.close();
        double[] r = new double[n]; //计算各种月饼的单价
        for(int k=0; k<n; k++) {
            r[k] = price[k] / stock[k];
            index[k] = k;
        }
	/*
	 * 按照单价排序
	 */
        double temp = 0;
        int x = 0;
        for(int i=0; i<n-1; i++) {
            for(int j=i+1; j<n; j++) {
                if(r[i] < r[j]) {
                    temp = r[i];
                    r[i] = r[j];
                    r[j] = temp;
                    x = index[i];
                    index[i] = index[j];
                    index[j] = x;
                }
            }
        }
	/*
	 * 将排序后的库存量和总售价存放在新的数组中
	 */
        double[] stock1 = new double[n];
        double[] price1 = new double[n];
        for(int i=0; i<n; i++) {
            price1[i] = price[index[i]];
            stock1[i] = stock[index[i]];
        }
        double maxValue = 0.0;
        int sum = 0;
        int i;
        for(i = 0; i < price.length; i++) {
            if(sum + stock1[i] < c) {
                sum += stock1[i];
                maxValue += price1[i];
            } else
                break;
        }
        if(i < price.length && sum < c) {
            maxValue += (double)(c - sum) / stock1[i] * price1[i];
        }
        System.out.println("月饼的最大收益是：" + maxValue);
    }
}

point

注意下月饼库存量和总售价可以是浮点数，总需求量也可以是浮点数。定义成 int 型的话，得到的结果怎么都不对………

正确结果示例：

结果