如何优化贪婪算法以最大化使用优惠券和有限资金购买的物品？

Question

我是算法初学者，我的母语不是英语，所以如果有任何认知错误或语法错误，请原谅我。

我正在解决一个问题，我需要使用一组优惠券和有限的钱来最大化我可以购买的物品数量。问题详细如下：

使用优惠券购物

您的购物清单上有 N 种商品，并且您有 N 种优惠券，可以在购买这些商品时节省一些钱。同时，你的口袋里还有D美元。您的目标是购买尽可能多的物品。

规则：

1. 每张优惠券可以使用多次，并且您可以购买每件商品多次。
2. 一张优惠券一次只能用于一件商品。
   • 例如，您可以使用优惠券

     A1

     购买商品

     B1

     ，然后使用优惠券

     A2

     购买商品

     B1

     ，但您不能再次使用优惠券

     A1

     购买商品

     B1

     。
3. 优惠券可以在不同的商品中重复使用。

示例：

假设有 4 种商品，价格分别为 $10、$12、$15 和 $20，以及 4 种优惠券，价值分别为 $6、$7、$8 和 $9。如果你的口袋里有$30，最好的策略是：

1. 购买 10 美元商品4 次，每张优惠券使用一次，费用为：
   10 * 4 - (6 + 7 + 8 + 9) = 10
2. 使用价值 7 美元、8 美元和 9 美元的优惠券购买 12 美元商品3 次，费用为：
   12 * 3 - (7 + 8 + 9) = 12
3. 使用 9 美元优惠券购买 15 美元商品，费用为：
   15 - 9 = 6
4. 您还剩 $2，这不足以购买更多物品。

因此，您可以购买的最大商品数量是8。

---

输入规格：

• 第一行包含两个整数：
  • N（<=10^5): The number of items and coupons.
  • D（<=10^6): The amount of money you have.
• 第二行包含N个正整数，代表商品的价格。
• 第三行包含N个正整数，代表优惠券的价值。

保证任何优惠券的最高价值小于任何商品的最低价格。

---

输出规格：

在一行中打印两个整数，用空格分隔：

1. 您可以购买的最大商品数量。
2. 剩余金额。

---

示例输入：

4 30
12 20 15 10
9 6 8 7

---

示例输出：

8 2 我尝试了一种天真的方法，通过从产品价格中减去优惠券来预先计算所有可能的有效价格，并按升序对它们进行排序，然后应用贪心策略，按升序获取有效价格，直到用完钱。然而，这会导致 O(N^2logu2061N) 复杂度，对于 N 高达 10^5 的此类算法问题来说，这太慢了。

这是我用 C 语言编写的简单代码。

#include <stdio.h>
#include <stdlib.h>

// Comparison function for qsort (ascending order)
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main(void) {
    int N, D; // N: number of items and coupons, D: total money available
    scanf("%d %d", &N, &D);

    // Arrays to store item prices and coupon discounts
    int price[N];
    int discount[N];

    // Input item prices
    for (int i = 0; i < N; i++) {
        scanf("%d", &price[i]);
    }

    // Input coupon discount values
    for (int i = 0; i < N; i++) {
        scanf("%d", &discount[i]);
    }

    // Array to store effective prices after applying discounts
    // This array has size N * N because each item can be paired with every coupon
    int PriceAfterDiscount[N * N];
    int index = 0; // Index to track the position in the array

    // Calculate all possible effective prices after applying discounts
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int currPrice = price[i] - discount[j]; // Price after applying coupon
            if (currPrice < 0) currPrice = 0;      // Ensure no negative prices
            PriceAfterDiscount[index++] = currPrice;
        }
    }

    // Sort the array of effective prices in ascending order
    qsort(PriceAfterDiscount, N * N, sizeof(int), compare);

    // Calculate the maximum number of items that can be bought
    int count = 0;     // Number of items bought
    int residue = D;   // Remaining money
    int i = 0;         // Pointer to iterate through the sorted prices

    // Greedy approach: buy items with the lowest effective prices first
    while (i < N * N && residue >= PriceAfterDiscount[i]) {
        residue -= PriceAfterDiscount[i]; // Deduct the price from the remaining money
        count++;                          // Increment the count of items bought
        i++;                              // Move to the next cheapest item
    }

    // Output the total number of items bought and the remaining money
    printf("%d %d\n", count, residue);

    return 0;
}

Answer 1

轻微；

避免溢出

*(int *)a - *(int *)b

 减法过程中存在溢出风险。

return (*(int *)a - *(int *)b); // Potential overflow 相反，比较一下：

return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b); // No overflow 各种编译器都能识别这种习惯用法并生成高效的代码。

// Or perhaps with a slightly more verbose, yet clear approach.
int compare(const void *a, const void *b) {
    const void *ia = a;
    const void *ib = b;
    return (ia > ib) - (ia < ib);
}