Do you need to sort inputs for dynamic programming knapsack -
in every single example i've found 1/0 knapsack problem using dynamic programming items have weights(costs) , profits, never explicitly says sort items list, in examples sorted increasing both weight , profit (higher weights have higher profits in examples). question when adding items in matrix item array/list, can add them in order, or add 1 smallest weight or profit? because multiple examples found i'm not sure if coincidence or in fact need put smallest weight/profit matrix each time
the dynamic programming solution nothing choosing possibilities(brute force) in efficient way(just saving them)... note consider subsets ... if list sorted or not , total number of subsets same subsets same , @ end subsets considered.. more or less if list order, wont matter...
Comments
Post a Comment