为什么贪心算法在这种情况下不起作用？

Question

我正在尝试解决以下SPOJ问题。

输入是：1.硬币中一定数量的钱的总重量，2.使用货币的硬币价值和相应的重量。

目标是找到给定金额的最小可能货币价值。

我的方法是按照它们的价值/重量比按升序排序货币硬币，然后贪心地将第一个硬币的重量适合于总和（跟踪它适合多少次），然后将第二个硬币的重量适合于余数尽可能多次，等等，对于所有硬币或直到余数为零（如果不是，则情况不可能）。

裁判说我的答案是错误的。您能否请提示一下算法有什么问题？

我的代码在此处：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int weight_t;
typedef unsigned int value_t;

struct coin {
    weight_t weight;
    value_t value;
    double value_per_gram;
};

coin make_coin(weight_t weight, value_t value) {
    coin ret;
    ret.weight = weight;
    ret.value = value;
    ret.value_per_gram = (double)(value/weight);
    return ret;
}

bool compare_by_value_per_gram(const coin& coin1, const coin& coin2) {
    return coin1.value_per_gram < coin2.value_per_gram;
}

int main() {
    unsigned int test_cases;
    cin >> test_cases;
    while(test_cases--) {
        unsigned int number_of_coins = 0;
        weight_t empty_pig, full_pig, coins_weight, coin_weight, min_value = 0;
        value_t coin_value = 0;
        vector<coin> coins;
        vector<unsigned int> how_many_coins;
        cin >> empty_pig >> full_pig;
        coins_weight = full_pig - empty_pig;
        cin >> number_of_coins;

        while(number_of_coins--) {
            cin >> coin_value >> coin_weight;
            coins.push_back(make_coin(coin_weight, coin_value));
        }
        sort(coins.begin(), coins.end(), compare_by_value_per_gram);

        how_many_coins.resize(coins.size());
        for(unsigned int i = 0; i < coins.size() && coins_weight > 0; i++) {
            how_many_coins[i] = coins_weight/coins[i].weight;
            coins_weight %= coins[i].weight;
            min_value += coins[i].value * how_many_coins[i];
        }
        if(coins_weight == 0) cout << "The minimum amount of money in the piggy-bank is " << min_value << "." << endl;
        else cout << "This is impossible." << endl;
    }
    return 0;
}

- mirgee

---

考虑到：如果你有美元、30美分、25美分、10美分、5美分和1美分硬币，那么贪心的最少硬币算法是行不通的。 - Hot Licks

假设你有重量相同的面额为2元和5元的硬币，需要支付6元。唯一的解决方案是使用3枚2元硬币，但若你先找到1枚5元硬币再找零，就会无法得到正确答案。 - cageman

我认为你应该使用动态规划而不是贪心算法。 - Jason Hu

银行里有3克硬币，其中1分钱的硬币重2克，2分钱的硬币重3克。 - n. m.

@mirgee，你有没有读过动态规划的相关内容？在任何一本好的算法书（例如Skiena）中都应该能找到相关章节。 - Colonel Panic

@ColonelPanic 感谢你的提示。不幸的是，我已经听说过了。问题在于我下意识地加入了这样的假设：没有相同重量的硬币和没有相同价值的硬币，这并没有被任何事情所暗示！我正在将这个问题应用到我所知道的唯一货币上。有趣的是，大脑是如何工作的，试图将它所知道的世界的限制应用到一个这些限制不需要存在的问题上。 - mirgee

Answer 1

一个简单的计数器示例将是两种类型的硬币 (重量，价值) = {(2,3)，(3,3)}，配有一个重量为4的存钱罐。您将尝试放置“更差”的硬币，重量为3，但无法匹配四个重量。但使用2 *（2,3）硬币的情况非常可能，

这可以通过类似于背包问题的方法解决，对动态规划解决方案进行一些修改：

思路是模仿穷举搜索。在每个步骤中，您查看当前候选硬币，有两个选择：取它或前进到下一个硬币。

f(x,i) = INFINITY          x < 0 //too much weight 
f(0,i) = 0                       //valid stop clause, filled the piggy completely.
f(x,0) = INFINITY          x > 0 //did not fill the piggy
f(x,i) = min{ f(x,i-1) , f(x-weight[i], i) + value[i] } //take minimal guaranteed value
               ^                  ^
        coin is not used      use this coin
            anymore

使用DP（自底向上或自顶向下）时，该解决方案的时间复杂度为O(n*W)，其中W是小猪的期望体重，n是货币中硬币的数量。

调用方式为f(Weight,#coins_in_currency)

- amit

---

这种穷举搜索方法不可行，因为对于某些输入会比较两个无限大数。但是你在维基百科链接中提到的无界背包问题的动态规划解决方案才是正确的方法。此处是我的尝试解决方案。 - mirgee

@mirgee 这个解决方案是背包问题的一个小变体。主要区别在于背包问题允许具有组合重量小于容量的物品，而这个问题则不行。如果对您没有起作用，则公式存在一些小的不准确之处，但总体方法是正确的，或者您的代码存在错误。 - amit