Блог пользователя DonMichaelCorleone

Printing solutions of Recursive DP problem
Автор DonMichaelCorleone, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 ^_^

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить