Why doesn't greedy approach work in this case?

Question

I am trying to solve the following SPOJ problem.

The input is: 1. Total weight of a certain amount of money in coins, 2. values and corresponding weights of the coins of used currency.

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

My approach is to sort the coins of the currency by their respective value/weight ratios in ascending order and then, greedily, fit the weight of the first coin as many times as possible in the total sum (keeping track of how many times it fits), then fit the weight of the second coin into the remainder as many times as possible, etc., for all the coins or until the remainder is zero (if it isn't, the situation is impossible).

The judge says my answer is wrong. Can you please give me a hint on what is wrong about 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 will be two types of coins (weight,value) = {(2,3), (3,3)}, with a piggy that weights 4. You will try to put the "worse" coin, with weight 3 and won't be able to match the weight of four. But the situation is very much possible with 2*(2,3) coins,

This can be solved very similarly to the knapsack problem, using some modification on the Dynamic Programming solution:

The idea is to mimic exhaustive search. At each step you look at the current candidate coin and you have two choices: take it, or advance 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

Invoke with f(Weight,#coins_in_currency)

Time complexity of this solution when using DP (bottom-up or top-down) is O(n*W) where W is the desired weight of the piggy and n is the number of coins in the currency.