Witam,
wałkuję zadanie ze SPOJa pod wesołym tytułem PiggyBank. Założenia są takie:
- podana jest waga skarbonki pustej i pełnej
- podane są wartości i wagi poszczególnych monet
- należy obliczyć minimalną wartość jaka może znajdować się w skarbonce
- jeśli nie można uzyskać z podanych monet wartości
full_pb - empty_pb
program ma wyświetlić "impossible"
Znalazłem w sieci algorytm plecakowy, a po dalszym szperaniu jego wersję dla min. wartości:
DP[i][j] ( j <= 0) = 0
DP[i][j] (i = 0, j > 0) = infinity
DP[i][j] (i > 0, j > 0) = min{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] },
Mój aktualny kod:
void PBank::evaluate()
{
int total_money_wt = full_pb - empty_pb;
std::vector<std::vector<int>> dp(currencies.size(), std::vector<int>(total_money_wt+1));
for (auto i = 0; i < currencies.size(); ++i)
{
for (int wt = 0; wt <= total_money_wt; ++wt)
{
if (wt == 0)
{
dp[i][0] = 0;
continue;
}
if (i == 0 && wt > 0)
{
dp[0][wt] = 500; // INT_MAX
continue;
}
if (wt - currencies[i - 1].weight < 0)
dp[i][wt] = 0;
else
dp[i][wt] = std::min(dp[i - 1][wt],
dp[i][wt - currencies[i - 1].weight] + currencies[i - 1].value);
}
}
std::cout << "\nmin val: " << dp[currencies.size()-1][total_money_wt];
}
Mam jakiś błąd bo nie wyświetla prawidłowej wartości. Np. dla ostatniego testu poniżej dostaję 2
Testy:
empty_pb = 10
full_pb = 110
currencies (val wt):
1 1
30 50
output --> 60empty_pb = 10
full_pb = 110
currencies (val wt):
1 1
50 30
output --> 100empty_pb = 1
full_pb = 6
currencies (val wt):
10 3
20 4
output --> "impossible"empty_pb = 2
full_pb = 10
currencies (val wt):
1 3
2 5
output --> 3