Variation on Knapsack problem...

[TheCPUWizard]

Here is the problem with a twist....

a) I have a number X of data objects I (items) ranging in size from 1...S. [each is Is]

b) I want to group them into a set of files (>1) that are all the same size C(Knapsack Capacity)
c) I want to use the smallest size knapsacks N , the has the minimum amount of wasted space.

Trivial (non-valid) solutions:

1) One single Knapsack that is Sum(Is). Obviously no wasted space, but does not meet the >1 criteria.

2) X knapsacks of size Smax. This will be the smallest possible size (a goal), but is likely to have significant wasted space....

X is <1000, and performance is not overly important (it can easily take up to one minute without causing a serious problem - obviously I would like it faster).

[Codeplug]

What's more important: minimizing file size or waste?

Does the problem need to be "solved", or is an approximation sufficient?

Should waste/overhead associated with the file-system be considered?

gg

[TheCPUWizard]

CodePlug,

Thanks for the response.

Approximations are definately OK.

The goal is to find the smallest size that has (nearly) the smallest amount of waste. Assume the following:

3 items, 600,300,100

1 sack size 1000 = 0 waste
2 sacks possible sizes 900, 700, 600 = Smallest is 400 with waste of 200
3 sacks size 600 waste of 300+500=800.

As the number of items N] increase so does the number of potential sack counts (win a minimum of 1 big one to N sacks where they size is just big enough for the largest item.

[dglienna]

2 sacks possible sizes 900, 700, 400 = Smallest is 400 with waste of 200

400 with 200 leftover, is that the same as

minimum amount of wasted space.

I'd think it wasn't allowed.

How do you put 600 # into a 400 # sack?

So, which is the correct choice above?

[Codeplug]

With 2 sacks: (600,300,)(100) or (600,100,)(300) or (600,)(300,100)
With waste: 800, 400, and 200 respectively

>> Smallest is 400 with waste of 200
I just read that as: minimum waste is grouping (600,)(300,100).

I've been trying to think of a dynamic programming solution, but it doesn't seem to break down into independent or overlapping "sub-problems" like other classic dynamic programming algorithms. So I'm thinking on how to characterize the brute-force/exhaustive search algorithm.

gg

[TheCPUWizard]

Sorry for the previous confusion....
ORIGINAL:

2 sacks possible sizes 900, 700, 600 = Smallest is 400 with waste of 200

900,700,600 are possible sack sizes which will satisfy the "packaging".

600 is obviously the smallest of these values. However one of the 2 sacks will only actually be holding 400, which means that there is 200 of empty space in the one sack....