DonMichaelCorleone's blog

Printing solutions of Recursive DP problem
By DonMichaelCorleone, history, 8 years ago, In English

How to print all the solutions of a knapsack DP problem solved by recursive manner ? Where every element can be picked more than one time.

I only can print the result ( like "yes"/"no", maximum sum/minimum cost etc, number of ways etc).

Sorry for my bad English.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well you can, instead of having just one array "dp[][].." make also another array "ans[][]...", where you will keep "even" (like what you did). You can keep there for example "7", like you kept 7 of actual element.

Afterward, you can execute function, which is very similar to your "dynamic programming function", anyway instead of making "multiple choices", you will do exactly what is written in "ans[][].." array.

This will lead you to "linear" simulation of BEST solution, where you will be at every node and you might print whatever you want there (for example "ans" or path or...)

Don't hesitate to ask more!

Good Luck & Have nice day ^_^

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you, I can now print the solution with ease :)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I don't understand the first paragraph. Can you clarify a bit more?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This means that you have another array (with same dimensions as your dp has), where you store information of "what was the best choice". Then you do recursion similar to your DP, but instead of "for cycle" which you had in DP, you simply travel by the "thing" you stored in the other array.

      I.e. if you are picking i-th item, and you find, optimal choice is to pick it X-times, you write: array[]..[]=X.. not you know exactly how many times you picked the item in optimal solution + the state to which you need to travel next (for printing purpose)

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

you can also just add another parameter ( a string) in the recursion to tell you what element you picked

so assume at this recursion step, you want to add 2 quantities of object number 2 to the knapsack, just append "22" to the resulting string, then you can either save it in another 2D array (like what user::-morass- said) , OR keep a global vector of string, once we found a solution, just push it to the global vector then print it in the main function

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    How to find the optimal solution from this global vector of string in linear time?

    → Reply