Why is there no greedy approach in this case?

Question

I am trying to solve the following SPOJ problem.

Input: 1. The total weight of a certain amount of money in coins, 2. The values ​​and the corresponding coin weights of the currency used.

The goal is to find the minimum possible monetary value of a given amount of money.

My approach is to sort the currency coins according to their respective ratio / weight ratios in ascending order, and then, greedily, pick up the weight of the first coin as many times as possible in total (tracking the number of times it fits), then set the weight second coin for the remaining amount as many times as possible, etc. for all coins or until the remainder is zero (if this is not so, the situation is impossible).

The judge says my answer is wrong. Could you give me a hint about what is wrong with the algorithm?

My code is here:

#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

A simple counter example would be two types of coins (weight,value) = {(2,3), (3,3)} , with a copy that weighs 4. You will try to put the “worst” coin with a weight of 3 and will not be able to match the weight four. But the situation is very possible with 2 * (2,3) coins,

This can be solved very similar to the knapsack problem using some changes in Dynamic Programming :

The idea is to simulate an exhaustive search. At each step, you look at the current coin of the candidate, and you have two options: take or go to the next coin.

 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 

Call with f(Weight,#coins_in_currency)

The time complexity of this solution when using DP (bottom to top or top to bottom) is O(n*W) , where W is the desired weight of the pig, and n is the number of coins in currency.