改進的動態揹包 - 有問題的輸入？

Question

以下是this SPOJ問題的嘗試解決方案。輸入是：

值和使用貨幣的硬幣對應的權重和目標

1. 硬幣一定數額的金錢的總重量是找的錢一定量的最小可能的貨幣價值。

我微微的揹包問題修改從wikipedia article揹包問題的動態規劃的解決方案 - 我只是第一個重量排序的硬幣，所以我沒有去通過所有的硬幣來獲得的最小值並且（希望）確保組合的重量等於容量。 （請看代碼，它非常簡單並且評論。）

但是，根據判斷，有一個輸入，我的算法給出了錯誤的答案。你能否建議算法有什麼問題？

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

Answer 1

的情況下empty_pig == full_pig是有問題的，因爲你已經忽略重複邏輯特殊殼體內的min_value_for_the_weight零條目。

另一個錯誤是，如果coins[j].weight > i只是break的好主意。舊代碼可能爲break，當coin[j].weight <= i和合並的另一半是錯誤的，即不可能製造重量爲i - coins[j].weight的硬幣。這發生在以下測試用例上。

1 
10 13 
2 
2 2 
3 3 

我們必須使用重量爲2或3的硬幣來製作重量3.重量1被正確確定爲不可能。重量2被正確確定爲可能的。對於重量3，我們嘗試重量2硬幣，確定重量1是不可能的，並且在嘗試重量3硬幣之前測試break。結果是代碼錯誤地報告說不可能使體重減輕3.