Reputation: 389
Following is an attempted solution to this SPOJ problem. The input is:
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;
}
Upvotes: 0
Views: 217
Reputation: 65516
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.
1
10 13
2
2 2
3 3
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.
Upvotes: 2