algorithmoptimizationdefragmentation

Defragmentation with minimum changes

I need to design an algorithm that does a simple defragmentation, but with the "minimum amount of changes" feature. Let's say I have 3 containers with capacity of 10 and following items in them:

Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1

All the containers are filled up to 8/10. Now i want to place next item of size 3 - the overall free capacity is 6, but none of the container has free capacity of 3. Although there are multiple possible solutions for doing defragmentation, I need the algorithm, that will find the solution, where item of size 2 from the 1st container will be placed somewhere else, so the new items can be then placed into container 1, since this solution requires only one change (instead of replacing two items from container 3). So the required result is supposed to be:

Container 1: 3 3 3(new item)
Container 2: 4 4 2(moved from Container 1)
Container 3: 1 5 1 1

I did some research already, all I could find was either Knapsack problem, or Buddy algorithm, but i am not sure, whether these are really what I am looking for.

Can anyone of you help me to design this algorithm as simple as possible? I am solving a situation where I will have low amount of large containers and huge amount of items in them, so enumerating all possibilities is not quite optimal.

Thanks a lot!

UPDATE Just to make clear what am I asking - it it no problem to determine whether the situation can be solved by doing one change only. The problem is, how to find the minimum amount of replacements when "one single move" is not possible.

Solution

  • This is not an answer to the question, but it is too long for a comment. The problem as stated here is NP-complete (once we've suitably changed it to a decision problem), reducible from the PARTITION problem.

    Let x1, x2, ..., xn be an instance of the PARTITION problem. For the sake of notation, let us take x1 to be the size of the smallest of the x's and let W be the sum of all the x's. Further, for the sake of simplicity let us assume that W is even.

    We construct an instance of the given problem to encode our PARTITION instance as follows. We have three containers of sizes W, W/2-x1, and x1. Initially, the first container contains items of sizes x1, x2, ..., xn and the other two are empty. The new item to be inserted is of size W/2. We observe that this new item can be inserted into these containers if and only if the original PARTITION problem has a solution.

    EDITED TO ADD (more proof detail)

    First, we suppose that we have a solution of the original PARTITION problem, i.e.: a split of the x's into two subsets S1 and S2 such that the sum of the x's in each subset are equal to W/2. Suppose that S1 contains x1, the smallest element. Then, we can move x1 into the third container and all the other elements of S1 into the second container, thus leaving a space of W/2 in the first container for the new item.

    Next, suppose that we have some way of inserting the new W/2-sized element into these containers. By inspection, the only way this can happen is by making space for it in the first container; and the only way that can happen is by moving exactly W/2 worth of items out of (and, consequently, leaving exactly W/2 worth of items in) the first container. Clearly, this defines a split of the original set of items into two subsets such that each subset has size W/2.

    Now, just because this problem is NP-complete doesn't mean that all is lost. It simply means that if you think you've come up with a solution that solves all instances in polynomial time, then you should probably check your work. The structure of the types of instances you will see (e.g.: "low amount of large containers and huge amount of items in them") may help guide the search for useful heuristics.