How to Find Which Elements Are in the Bag, Using Knapsack Algorithm [And Not Only the Bag'S Value]

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

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.

Printing Items that are in sack in knapsack

From your DP table we know f[i][w] = the maximum total value of a subset of items 1..i that has total weight less than or equal to w.

We can use the table itself to restore the optimal packing:

def reconstruct(i, w):  # reconstruct subset of items 1..i with weight <= w
                        # and value f[i][w]
  if i == 0: 
      # base case
      return {}
  if f[i][w] > f[i-1][w]:
      # we have to take item i
      return {i} UNION reconstruct(i-1, w - weight_of_item(i))
  else:
      # we don't need item i
      return reconstruct(i-1, w)

Knapsack with multiple bags and items having only weight

This is known as the bin packing problem (which is NP-hard).

By simply sorting the decreasing order by their sizes, and then inserting each item into the first bin in the list with sufficient remaining space, we get 11/9 OPT + 6/9 bins (where OPT is the number of bins used in the optimal solution). This would easily take O(n²), or possibly O(n log n) with an efficient implementation.

In terms of optimal solutions, there isn't a dynamic programming solution that's as well-known as for the knapsack problem. This resource has one option - the basic idea is:

D[{set}] = the minimum number of bags using each of the items in {set}

Then:

D[{set1}] = the minimum of all D[{set1} - {set2}] where set2 fits into 1 bag
                                                  and is a subset of set1

The array index above is literally a set - think of this as a map of set to value, a bitmap or a multi-dimensional array where each index is either 1 or 0 to indicate whether we include the item corresponding to that dimensional or not.

The linked resource actually considers multiple types, which can occur multiple times - I derived the above solution from that.

The running time will greatly depend on the number of items that can fit into a bag - it will be O(minimumBagsUsed.2maxItemsPerBag).

In the case of 1 bag, this is essentially the subset sum problem. For this, you can consider the weight the same as value and solve using a knapsack algorithm, but this won't really work too well for multiple bags.

Why not? Consider items 5,5,5,9,9,9 with a bag size of 16. If you just solve subset sum, you're left with 5,5,5 in one bag and 9 in one bag each (for a total of 4 bags), rather than 5,9 in each of 3 bags.

Subset sum / knapsack is already a difficult problem - if using it's not going to give you an optimal solution, you may as well use the sorting / greedy approach above.

Getting list of selected items in Knapsack DP matrix

 w =  w - wt[i-1] 

is actually

w =  w - wt[i-2] 

since the i = i - 1 is computed before it.
Below code will work now.

    weight += wt[i-1];
    i = i - 1;
    w = w - wt[i] ;

Algorithm for Filling bag maximally (this is not the knapsack 0/1)

In this particular instance you get maximum benefit by minimizing the free space in the bag and therefore by considering weight as a value. This problem is commonly referred to as subset sum problem and is a particular case of knapsack problems family.

The DP relation looks like the following

where at each step you try to find the maximum value (which does not exceed the bag's capacity) among the previous elements set plus the new element

A C++ implementation of the subset sum problem to answer the question "can I fill the bag entirely given these elements?" and driver follows

bool ssp(const vector<int>& v, const int& N) {

  vector<vector<int>> m( v.size() + 1 /* 1-based */,
                         vector<int>(N + 1 /* 1-based */, 0) );

  // The line above also took care of the initialization for base
  // cases f(i,0) = 0 and f(0,b) = 0

  for (int i = 1; i <= v.size(); ++i) { // For each subset of elements
    for (int b = 1; b <= N; ++b) { // For each subcapacity
      int opt1 = m[i - 1][b];
      int opt2 = -1;
      if (b - v[i - 1] >= 0) { // No caching to keep this readable
        opt2 = m[i - 1][b - v[i - 1]] + v[i - 1];
        if (opt2 > b)
          opt2 = -1; // Not allowed
      }
      m[i][b] = max(opt1, opt2);
    }
  }

  return (m[v.size()][N] == N);
}

int main() {

  const vector<int> v = { 1, 3, 7, 4 };
  const int N = 11;

  cout << "Subset sum problem can be solved with the given input: "
       << boolalpha << ssp(v, N); // true

  return 0;
}

The complexity is O(N⋅I) where I is the number of elements in the starting set. This is a pseudopolynomial complexity.

Source: Knapsack problem

---

Related Topics