Hva er 0/1 knapsack?
Klikk for å snu kortet
Velg gjenstander med vekt wiw_iwi og verdi viv_ivi, maks kapasitet WWW. DP: dp[i][w]=max(dp[i−1][w],dp[i−1][w−wi]+vi)dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i]+v_i)dp[i][w]=max(dp[i−1][w],dp[i−1][w−wi]+vi). Tid: O(nW)O(nW)O(nW).
Space / Enter for å snu