Variation on knapsack – minimum total value exceeding ‘W’

by

let TOT = w1 + w2 + ... + wn.

In this answer I will describe a second bag. I’ll denote the original as ‘bag’ and to the additional as ‘knapsack’

Fill the bag with all elements, and start excluding elements from it, ‘filling’ up a new knapsack with size of at most TOT-W, with the highest possible value! You got yourself a regular knapsack problem, with same elements, and bag size of TOT-W.

Proof:

Assume you have best solution with k elements: e_i1,e_i2,...,e_ik, then the bag size is at least of size W, which makes the excluded items knapsack at most at size TOT-W. Also, since the value of the knapsack is minimized for size W, the value of the excluded items is maximized for size TOT-W, because if it was not maximized, there would be a better bag of size at least W, with smaller value.

The other way around [assuming you have maximal excluded bag] is almost identical.

More Related Contents:

  1. Knapsack with multiple bags and items having only weight
  2. What does O(log n) mean exactly?
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Generate an integer that is not among four billion given ones
  5. How to generate Sudoku boards with unique solutions
  6. Time complexity of Euclid’s Algorithm
  7. Quick sort Worst case
  8. How to round floats to integers while preserving their sum?
  9. Modulus power of big numbers
  10. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  11. Fast algorithm implementation to sort very small list
  12. Compute social distance between two users
  13. Efficient algorithm for ordering different types of objects
  14. How to find two most distant points?
  15. Smooth spectrum for Mandelbrot Set rendering
  16. Algorithm to find two repeated numbers in an array, without sorting
  17. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  18. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  19. Determining if two line segments intersect? [duplicate]
  20. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  21. Mesh generation from points with x, y and z coordinates
  22. How to find distance from the latitude and longitude of two locations?
  23. Algorithm for sampling without replacement?
  24. Bits counting algorithm (Brian Kernighan) in an integer time complexity
  25. Non-Recursive Merge Sort
  26. Reversing CRC32
  27. Planar Graph Layouts
  28. Optimized low-accuracy approximation to `rootn(x, n)`
  29. What are probabilistic data structures?
  30. Connected Component Labeling – Implementation

Leave a Comment