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;
}

Izaguirre

Consider: A greedy least-number-of-coins algorithm won't work if you have dollar, 30 cent, 25 cent, 10 cent, 5 cent, and 1 cent coins. – Ronel

simple case you have coins of 2 and 5 (same weight) you need to pay 6. Only solution here is 3 times 2, but you would find 5 first and afterwards fail to find the correct answer? – Skin

i think you should use DP instead of greedy. – Cathouse

3 gram of coins in a bank, 1 cent 2 gram coins and 2 cent 3 gram coins. – Crimson

@Izaguirre Have you ever read about dynamic programming? You should find a chapter about it in any good algorithms book (eg. Skiena). – Trussell

@ColonelPanic Thanks for the tip. Sadly, I've heard of it. The problem here is that I subconsciously added the supposition that there are no coins of the same weight and no coins of the same value, which is not implied by anything! I was applying the problem to the only currency I know. Funny, how the brain works, trying to apply the constraints of the world it knows to a problem where these constraints need not exist. – Izaguirre

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.

Promisee

This exhaustive search approach doesn't work, since for some inputs it ends up comparing two infinities. But the dynamic programming solution to the unbounded knapsack problem from your wikipedia link is the way to go. Here is my attempted solution. – Izaguirre

@Izaguirre This solution is a slight variation of knapsack. The main different is knapsack allows to have items with combined weight less than the capacity, and this problem does not. If it did not work for you then there is a small inaccuracy in the formula, but the general approach is correct or you had a bug in the code. – Promisee