For an assignment I have been given the bin packing problem and asked to show how you can solve the decision version of the problem from the optimization version and vice versa. I understand that to solve the decision version you simply take the number of bins used in the optimization version and compare it to the max number of bins specified but how can I use the decision version to solve the optimization version?
Related Questions in ALGORITHM
- Add image to JCheckBoxMenuItem
- How to access invisible Unordered List element with Selenium WebDriver using Java
- Inheritance in Java, apparent type vs actual type
- Java catch the ball Game
- Access objects variable & method by name
- GridBagLayout is displaying JTextField and JTextArea as short, vertical lines
- Perform a task each interval
- Compound classes stored in an array are not accessible in selenium java
- How to avoid concurrent access to a resource?
- Why does processing goes slower on implementing try catch block in java?
Related Questions in OPTIMIZATION
- Add image to JCheckBoxMenuItem
- How to access invisible Unordered List element with Selenium WebDriver using Java
- Inheritance in Java, apparent type vs actual type
- Java catch the ball Game
- Access objects variable & method by name
- GridBagLayout is displaying JTextField and JTextArea as short, vertical lines
- Perform a task each interval
- Compound classes stored in an array are not accessible in selenium java
- How to avoid concurrent access to a resource?
- Why does processing goes slower on implementing try catch block in java?
Related Questions in BIN-PACKING
- Add image to JCheckBoxMenuItem
- How to access invisible Unordered List element with Selenium WebDriver using Java
- Inheritance in Java, apparent type vs actual type
- Java catch the ball Game
- Access objects variable & method by name
- GridBagLayout is displaying JTextField and JTextArea as short, vertical lines
- Perform a task each interval
- Compound classes stored in an array are not accessible in selenium java
- How to avoid concurrent access to a resource?
- Why does processing goes slower on implementing try catch block in java?
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Popular Tags
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
You can use the decision version to solve the optimization version by observing that if
N
bins is sufficient, thenK > N
bins will also be sufficient.Start with a single bin, and run the decision version on it. If the answer is
true
, you are done; otherwise, keep doubling the number of bins until you hit atrue
. Let's say that you get an answer oftrue
when you tryN = 2 ^ k
. Then you can run a binary search betweenM = 2^(k-1)
andN
, inclusive, to find the exact solution to the optimization problem (bothN
andk
come from the previous step).Consider this example: let's say the optimal solution is 14. You could then try the following sequence of decision problem to find the answer:
false
false
(doubled 1)false
(doubled 2)false
(doubled 4)true
(doubled 8; we've got atrue
, so proceed to the binary search)false
(midpoint between 8 and 16)true
(midpoint between 12 and 16)false
(midpoint between 12 and 14)In general, the answer can be found in logarithmic time (i.e. in Log2(Answer)).
Once you know the number of bins
N
required to packageX
objects, run a bipartite matching algorithm between the items on one side and theN
bins on the other side. Assuming that the decision problem is solved correctly, such bipartite matching must exist, and can be found in polynomial time.