Witam,
uczę się algorytmów ze strony kompendium.meetit.pl
w programowaniu dynamicznym jest taki kod:
bool DP[MAXW + 1];
for (int i=1; i<=w; ++i) DP[i] = 0;
DP[0] = 1;
for (int i=1; i<=n; ++i) {
int k = a[i];
for (int j=0; j<=w-k; ++j)
if (DP[j] == 1)
DP[j + k] = 1;
}
w poradniku jest napisane, że jest w nim błąd i należy go znaleźć
wiem co powoduje ten błąd (nie sprawdza, czy suma została utworzona przy użyciu liczby k), wiem jak to naprawić, ale potrzebowałbym do tego dodatkowej tablicy, jak naprawić ten błąd najkrócej?