Ниже приводится попытка решения этот SPOJ проблема. Ввод:
Я немного изменил динамическое программирование решения проблемы ранца из статья в википедии о проблеме с рюкзаком — я просто сначала отсортировал монеты по весу, чтобы мне не нужно было проходить все монеты, чтобы получить наименьшее значение, и (надеюсь) убедился, что общий вес равен емкости. (Пожалуйста, посмотрите код, он действительно прост и прокомментирован.)
Однако, по словам судьи, есть вход, на который мой алгоритм дает неверный ответ. Подскажите, пожалуйста, что не так с алгоритмом?
#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;
}
Дело empty_pig == full_pig
проблематично, потому что вы забыли повторить специальный логику в нулевой записи min_value_for_the_weight
,
Другая ошибка в том, что это хорошая идея break
если coins[j].weight > i
, Старый код мог break
когда coin[j].weight <= i
а другая половина конъюнктуры была ложной, то есть невозможно было делать монеты весом i - coins[j].weight
, Это происходит в следующем тестовом примере.
1
10 13
2
2 2
3 3
Мы должны сделать вес 3, используя монеты весом 2 или 3. Вес 1 правильно определен как невозможный. Вес 2 правильно определен, чтобы быть возможным. Для веса 3 мы попробуем монету с весом 2, определим, что вес 1 невозможен, и break
перед тем, как попробовать монету весом 3. В результате код ошибочно сообщает, что невозможно сделать вес 3.