Close to knapsack problem?

Question

I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though.

Please see the input given below and my solution. There are three types of items and 4 buckets. The problem is to keep the items as uniformly as possible in the 4 buckets. i.e. the capacity of the buckets (or number of items in the bucket) should be equal (or close to equal). You can also keep the items from different types in the same bucket.

example input:

item-type   :   A   B   C
  #items    :   12  36  25

One simple solution I am using currently is as follows:

1. Since there are 4 buckets, each bucket should get (sum of items)/4. For the above example input data, it is (12 + 36 + 25)/4, i.e. approximately 18 items. The capacity of each of the bucket should be "CLOSE" to 18.

2. Then start keeping the items of type A into the first bucket until the number of items become 18. However, still we need 6 more items for the first bucket as the number of type A items are 12. Therefore keep 6 items of the type B into the first bucket so that the capacity of the first bucket will be 18. Like this fill the other three buckets also.

Finally the four buckets are as follows:

Bucket-1: (12 A items, 6 B items)
Bucket-2: (18 B items)
Bucket-3: (12 B items, 6 C items)
Bucket-4: (19 C items).

I think that the time complexity of this problem is O(N^2), N is the number of buckets.

It would be great if someone helps me to improve the solution further.

Note-1: We can mix items of different types in the same bucket.

Note-2: We also need to somehow keep the information of type of the item in the bucket.

Answer 1

It looks like all your items have the same size, in which case the solution is trivial. Count the total number of items, let's say that number is c. Say there are n buckets. Calculate x = floor (c / n) and y = c - n*x. Then y bins get filled with x+1 items, and n-y bins filled with x items.

To make this an interesting problem, assume that the different item types have different sizes, and assume this time the total of all weights is c. In that case, it is quite possible that you cannot distribute the items into bins with weights x and x+1. Or that it is hard to do so. If it is impossible, then you'd need to define what the "best" solution is.

Answer 2

For item quantities A, B, C and buckets quantity N, each bucket should keep close to A/N + B/N + C/N items, respectively of each kind. Actual putting the items should take O(N).

You can distribute A mod N + B mod N + C mod N items slightly unevenly among buckets using round-robin choice: put a remaining item of type A into bucket #1, remaining item of type B into bucket #2, etc, wrap to bucket #1 as needed. A clever use of mod operator should make this O(N), too.

Answer 3

Wouldn't you want to iterate through the number of total items and not buckets^2?

For example,

item[0] goes into bucket 1.
item[1] goes into bucket 2.
item[2] goes into bucket 3.
item[3] goes into bucket 4.
item[4] goes into bucket 1.

Some things to think about: Does each item have a property, item-type as part of its definition? For example, you know a red marble, is red. Are the items sorted?