title: Dual knapsack algorithm
body: <p>Say you have a warehouse with fragile goods (f.e. vegetables or fruits), and you can only take out a container with vegetables once. If you move them twice, they'll rot too fast and cant be sold anymore.</p>
  
  <p>So if you give a value to every container of vegetables (depending on how long they'll still be fresh), you want to sell the lowest value first. And when a client asks a certain weight, you want to deliver a good service, and give the exact weight (so you need to take some extra out of your warehouse, and throw the extra bit away after selling).</p>
  
  <p>I don't know if this problem has a name, but I would consider this the dual form of the knapsack problem. In the knapsack problem, you want to maximise the value and limit the weight to a maximum. While here you want to minimise the value and limit the weight to a minimum.</p>
  
  <p>You can easily see this duality by treating the warehouse as the knapsack, and optimising the warehouse for the maximum value and limited weight to a maximum of the current weight minus what the client asks.</p>
  
  <p>However, many practical algorithms on solving the knapsack problem rely on the assumption that the weight you can carry is small compared to the total weight you can chose from. F.e. the <a href="https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem" rel="nofollow">dynamic programming 0/1</a> solution relies on looping until you reach the maximum weight, and the <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Fully_polynomial_time_approximation_scheme" rel="nofollow">FPTAS</a> solution guarantees to be correct within a factor of (1-e) of the total weight (but a small factor of a huge value can still make a pretty big difference).</p>
  
  <p>So both have issues when the wanted weight is big.</p>
  
  <p>As such, I wondered if anyone studied the "dual knapsack  problem" already (if some literature can be found around it), or if there's some easy modification to the existing algorithms that I'm missing.</p>