我正在尝试解决以下问题 SPOJ problem .
输入是: 1.总重量一定的钱币, 2. 使用币种的币值及对应权重。
目标是找到给定金额的最小可能货币值(value)。
我的方法是将货币的硬币按各自的值(value)/重量比升序排序,然后贪婪地在总和中尽可能多地拟合第一个硬币的重量(跟踪有多少次),然后将第二枚硬币的重量尽可能多地放入余数中,以此类推,对于所有硬币或直到余数为零(如果不是,则这种情况是不可能的)。
法官说我的回答是错误的。你能给我一个关于算法错误的提示吗?
我的代码在这里:
#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;
}
最佳答案
一个简单的反例是两种类型的硬币(weight,value) = {(2,3), (3,3)}
,带有小 pig 重量为 4。您将尝试放入重量为 3 的“更差”硬币,但无法匹配重量为 4 的硬币。但是对于 2*(2,3) 个硬币,这种情况很有可能发生,
这可以与 knapsack problem 非常相似地解决。 , 在 Dynamic Programming 上使用一些修改解决方案:
这个想法是模仿穷举搜索。在每一步中,您都会查看当前的候选代币,您有两个选择:接受它,或者前进到下一个代币。
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(Weight,#coins_in_currency)
当使用 DP(自下而上或自上而下)时,此解决方案的时间复杂度为 O(n*W)
,其中 W
是所需的小 pig 重量n
是货币中硬币的数量。
关于c++ - 为什么贪婪的方法在这种情况下不起作用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25493245/