4 ms·
I understand your solution, but is it really "Dynamic Programming"? DP requires that the problem can be broken down into subproblems. Also your method requires
by AlexanderTheGr8 5y ago
I understand your solution, but is it really "Dynamic Programming"? DP requires that the problem can be broken down into subproblems. Also your method requires just quadratic time, right? (It's still pseudo-polynomial though.)
I think it should take quadratic time because for every item you find, you loop through the entire array, and whenever you see a 'True', you add the current item's price in it and make that new entry 'True'. You do this for all 'N' items and then in the end, check whether the last index in the array is 'True'.
Did I miss something?
- lrem 5y agohttps://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... calls it dynamic programming.
- deleted 5y ago[deleted]
- xxs 5y agoThe integer version of knapsack one is considered dynamic programming (use cents to represent the dollar value). It's pseudo polynomial - it's effectively O(TotalWeight * Items) if the items can be added once only.
- deleted 5y ago[deleted]
- Cu3PO42 5y agoI also know this approach as Dynamic Programming. While the subproblem is not cleanly seperated it is present in the sense that you consider one element first and then deal with the rest later, never touching the first again. And yes, the runtime here is polynomial, however it is polynomial in the price k, which only needs log k bits to encode in the input. Therefore it is exponential in the encoding length. These algorithms are called pseudo-polynomial.
- H8crilA 5y agoThe subproblem is covering $0.00 (always possible), then covering $0.01, then covering $0.02, then covering $0.03, ... Yeah the time complexity is O(N*M), where N is the value of the target added up price (size of the unary representation), and M is the number of items.