How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?

by

Getting the elements you packed from the matrix can be done using the data from the matrix without storing any additional data.

Pseudo code:

line <- W
i <- n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
      // the element 'i' is in the knapsack
      i <- i-1 // only in 0-1 knapsack
      line <- line - weight(i)
  else: 
      i <- i-1

The idea behind it is that you iterate the matrix; if the weight difference is exactly the element’s size, it is in the knapsack. If it is not, the item is not in the knapsack, go on without it.

More Related Contents:

  1. How to find number of words in a phrase with spaces removed by checking v. dictionary
  2. What is the most effective way for float and double comparison?
  3. How to implement classic sorting algorithms in modern C++?
  4. Fast bignum square computation
  5. Detecting endianness programmatically in a C++ program
  6. Determine if two rectangles overlap each other?
  7. Algorithm to convert RGB to HSV and HSV to RGB in range 0-255 for both
  8. What is the efficient way to count set bits at a position or lower?
  9. Fast exact bigint factorial
  10. Generating combinations in c++
  11. Rounding up to the nearest multiple of a number
  12. Magic number in boost::hash_combine
  13. Creating all possible k combinations of n items in C++
  14. Where can I get a “useful” C++ binary search algorithm?
  15. How to get a random element from a C++ container?
  16. LRU cache design
  17. c++ sort keeping track of indices [duplicate]
  18. Determining if a number is prime
  19. How to add two numbers without using ++ or + or another arithmetic operator
  20. Are there any better methods to do permutation of string?
  21. Reorder vector using a vector of indices [duplicate]
  22. Converting epoch time to “real” date/time
  23. Fastest algorithm for primality test [closed]
  24. What is the safe way to fill multidimensional array using std::fill?
  25. Cut set of a graph, Boost Graph Library
  26. What’s time complexity of this algorithm for finding all combinations?
  27. Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]
  28. Good C++ solutions to the “Bring all the zeros to the back of the array” interview challenge
  29. Finding square root without using sqrt function?
  30. Order Statistic Tree in C++

Leave a Comment