为什么贪婪的方法在这种情况下不起作用？

Question

输入是：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;
}

Answer 1

一个简单的反例是两种硬币（重量，价值）={（2,3），（3,3）}，其中一只小猪的重量为4。您将尝试放置“更差”的硬币，重量为3，但无法匹配4的重量。但这种情况很可能发生在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

使用f（重量，#货币中的#硬币）

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