We have unlimited number of bins each of capacity 1, and n objects of sizes s1,

Question

We have unlimited number of bins each of capacity 1, and n objects of sizes s1, s2, ..., sn, where 0 < si 1. Our job is to pack these objects into bins using the fewest bins possible (optimization). The decision version can be stated as follows: given n objects and k, is there a packing using no more than k bins. Show how to solve one version if you know how to solve the other version, i.e., show how to solve the decision version by solving the optimization version and show how to solve the optimization version by solving the decision version.

Explanation / Answer

Our initial step will be to start having only a single bin and use the decision version on it. If the response is "Yes", we achieved our required step. otherwise, we have to double the number of bins until we have to get a "Yes". We will find a "Yes" when we are trying the doubling for the number of the bins .

For example:

The optimal solution is 14. We can try like this for the answer:

The answer can be found in Log2(Answer)).

There is also another better mechanism for finding the solution for the optimization problem based on the decision problem, If our answer is exponential in the size of the input, then we can have an algorithm that results in T(n) on the decision problem, the solution rusults in O(k*T(n)), but k is an exponential in the size of the input we are required only log(k) bits for producing it.

We can also try a binary search to find the exact solution to the optimization problem and there will be required only O(logk) steps for packing objects into bin.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.