Bin Packing or Knapsack?

Question

I'm having some issues with an assignment I have. I've been searching stackoverflow and other websites to see which kind of problem I'm dealing with, and turns out I'm not sure if it's a knapsack problem or a bin packing problem. Here's the problem:

An old lady bought N products, each product with a different weight (kg), and she wants to fit it all into a bag that can hold K kg. Find the set of objects that the sum of the weights gets as close as it can to K.

Apocynaceous

Answer 1

This is a special case of the knapsack problem where each item's value is equal to its weight. (In general knapsack problems, you may be maximizing the total "value" of all the objects as defined by the problem -- perhaps their monetary value in a physical problem, or desirability to the user when scheduling programs or tasks.)

From Wikipedia,

When the number of bins is restricted to 1 and each item is characterised by both a volume and a value, the problem of maximising the value of items that can fit in the bin is known as the knapsack problem.

So you could consider it a special case of bin-packing, as well ("volume" being the item's weight).

Joellajoelle

Answer 2

In the one hand, Knapsack problem is defined, in general, as follow:

Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

In the other hand, Bin packing problem is defined, in general, in this form:

Objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.

So, your problem is knapsack problem as far as I know.

I did not make a lot of effort to answer your question since it is a copy-paste from wikipedia which you can do by reading the links that I gave you.

Foretopmast

Answer 3

It is a simple case of the knapsack problem. In general, the items would have both a weight and a value, and you are asked to find items where the total weight fits and the total value is maximised; in your case the value is equal to the weight.

The bin packing problem asks to put all items into the smallest possible number of bins.

You could have similar but more difficult problems, like choosing items to be put into a fixed set of containers of possibly different sizes. I don't think that problem would have a name.

Unifilar