Modified dynamic knapsack - problematic input?

Question

Following is an attempted solution to this SPOJ problem. The input is:

Total weight of a certain amount of money in coins
values and corresponding weights of the coins of used currency and the goal is to find the minimum possible monetary value of the given amount of money.

I slightly modified a dynamic programming solution of the knapsack problem from the wikipedia article on the knapsack problem - I just first sorted the coins by weight so I don't have to go through all the coins to get the smallest value and (hopefully) made sure that the combined weight is equal to the capacity. (Please, see the code, it's really simple and commented.)

However, according to the judge, there is an input for which my algorithm give an incorrect answer. Can you please suggest what is wrong with the algorithm?

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

typedef unsigned int weight_t;
typedef unsigned int value_t;

struct coin {
    weight_t weight;
    value_t value;
};

coin make_coin(weight_t weight, value_t value) {
    coin ret;
    ret.weight = weight;
    ret.value = value;
    return ret;
}

bool compare_by_weight(const coin& coin1, const coin& coin2) {
    return coin1.weight < coin2.weight;
}

int main() {
    unsigned int test_cases;
    cin >> test_cases;
    while(test_cases--) {
        //Initialization
        unsigned int number_of_coins, n = 0;
        weight_t empty_pig, full_pig, coin_weight, coins_weight;
        value_t coin_value, min_value, current_value = 0;
        vector<coin> coins;
        vector<unsigned int> min_value_for_the_weight;

        //Input
        cin >> empty_pig >> full_pig;
        cin >> number_of_coins;
        n = number_of_coins;
        while(n--) {
            cin >> coin_value >> coin_weight;
            coins.push_back(make_coin(coin_weight, coin_value));
        }

        //Input processing
        coins_weight = full_pig - empty_pig;
        sort(coins.begin(), coins.end(), compare_by_weight);
        min_value_for_the_weight.resize(coins_weight+1);
        for(unsigned int i = 0; i < coins_weight; i++) min_value_for_the_weight[i] = 0;

        //For all weights
        for(unsigned int i = 1; i <= coins_weight; i++) {
            //Find the smallest value
            min_value = numeric_limits<value_t>::max();
            for(unsigned int j = 0; j < number_of_coins; j++) {
                //The examined coin weights more or same than examined total weight and we either already have put a coin
                //in, or this is the first one
                if(coins[j].weight <= i && (min_value_for_the_weight[i - coins[j].weight] > 0 || i == coins[j].weight)){
                    current_value = coins[j].value + min_value_for_the_weight[i - coins[j].weight];
                    if(current_value < min_value) min_value = current_value;
                } else break;  // <- this I deleted to get accepted
            }
            if(min_value == numeric_limits<value_t>::max()) min_value = 0;
            min_value_for_the_weight[i] = min_value;
        }

        //If the piggy empty, output zero
        if(!min_value_for_the_weight[coins_weight] && coins_weight != 0)
            cout << "This is impossible." << endl;
        else
            cout << "The minimum amount of money in the piggy-bank is " << min_value_for_the_weight[coins_weight] << "." << endl;
        }
    return 0;
}

David Eisenstat David Eisenstat · Accepted Answer · 2014-08-28T22:40:53

The case empty_pig == full_pig is problematic, because you have neglected to repeat the logic special-casing the zeroth entry of min_value_for_the_weight.

The other bug is that it's only a good idea to break if coins[j].weight > i. The old code could break when coin[j].weight <= i and the other half of the conjunct was false, i.e., it was impossible to make coins with weight i - coins[j].weight. This happens on the following test case.

We have to make weight 3 using coins of weight 2 or 3. Weight 1 is correctly determined to be impossible. Weight 2 is correctly determined to be possible. For weight 3, we try the weight-2 coin, determine that weight 1 is impossible, and break before trying the weight-3 coin. The result is that the code erroneously reports that it's impossible to make weight 3.

Modified dynamic knapsack - problematic input?

1 Answers