Problem plecakowy dla wartości minimalnych

0

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 --> 60

empty_pb = 10
full_pb = 110
currencies (val wt):
1 1
50 30
output --> 100

empty_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

0

to nie jest problem plecakowy, choć wygląda podobnie!
Wagę masz sztywno ustaloną, najpierw musisz ustalić czy da się uzyskać dokładnie tą wagę.
W problemie plecakowym masz maksymalną dopuszczalną wagę (może zostać puste miejsce) a dopiero potem odszukać minimalną wartość.
Tak samo, każdy rodzaj monety masz nielimitowaną ilość, w problemie plecakowym są ustalone limity dostępności.

0

W międzyczasie znalazłem coś takiego LINK i takiego LINK2

Dzisiaj nie miałem czasu usiąść do tego i coś wykodzić, ale wydaje mi się, że jest to do zrobienia przez Unbounded Knapsack Problem tylko po prostu coś źle implementuję.

0

Udało mi się napisać kod, który daje prawidłowe wartości dla moich testów oraz tych podanych na stronie, ale na SPOJu wysypuje się z błędem runtime error (SIGSEGV)
Może ktoś rzucić okiem ?
W komentarzach pod zadaniem wyczytałem, żeby tablicę dp utworzyć globalnie, ale najwyraźniej to nie tu leży problem.

https://www.spoj.com/problems/PIGBANK/

https://ideone.com/X4Yf6K

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0