a
To prove the problem of determining the minimum number of bins required is NP-HARD.
a
Explanation of Solution
Suppose and are the same (indeed if the answer is yes for. Then there exists . On the other hand if the answer is yes for , so if
Note that
So, the answer of derived bin-packing problem can-not be less than 2 . First assume that the answer to the given instance of sub set -sum problem is “yes”.
Now, there is
Now
b
To argue that the optimal number of bins required is at least
b
Explanation of Solution
Consider the packing ofn objects with sizes
Let
Therefore,
Since bis an integer number,
c
To argue that the first-fit heuristic leaves at most one bin less than half full.
c
Explanation of Solution
The first- fit heuristic places each object in the first available bin. Suppose by contradiction that two bins
d
To prove that the number of bins used by the first-fit heuristic is never more than
d
Explanation of Solution
Consider a bin- packing solution provided by the first-fit HEURISTIC.
Using similar notation as in (b) (let
It can be assumed without loss of generality that
e
To prove an approximation ratio of 2 for the first-fit heuristic.
e
Explanation of Solution
Letb be the number of the bins used the first-fit HEURISTIC and let
e
To give an efficient implementation of the first-fit heuristic, and analyze its running time.
e
Explanation of Solution
1.
2. initialize data structures
3. fori = 1 to ndo
4. letjbe the first bin that can fit objecti with size
5. ifjexists then
6. inserti at the list (list
7.update data structures
8.else
9.
10. insertiat the list
11.update data structures II
12.endif
13. endfor
Each of the above steps can be done in
Want to see more full solutions like this?
Chapter 35 Solutions
Introduction to Algorithms
- Scenario You work for a small company that exports artisan chocolate. Although you measure your products in kilograms, you often get orders in both pounds and ounces. You have decided that rather than have to look up conversions all the time, you could use Python code to take inputs to make conversions between the different units of measurement. You will write three blocks of code. The first will convert kilograms to pounds and ounces. The second will convert pounds to kilograms and ounces. The third will convert ounces to kilograms and pounds. The conversions are as follows: 1 kilogram = 35.274 ounces 1 kilogram = 2.20462 pounds 1 pound = 0.453592 kilograms 1 pound = 16 ounces 1 ounce = 0.0283 kilograms 1 ounce = 0.0625 pounds For the purposes of this activity the template for a function has been provided. You have not yet covered functions in the course, but they are a way of reusing code. Like a Python script, a function can have zero or more parameters. In the code window you…arrow_forwardmake a screen capture showing the StegExpose resultsarrow_forwardWhich of the following is not one of the recommended criteria for strategic objectives? Multiple Choice a) realistic b) appropriate c) sustainable d) measurablearrow_forward
- Management innovations such as total quality, benchmarking, and business process reengineering always lead to sustainable competitive advantage because everyone else is doing them. a) True b) Falsearrow_forwardVision statements are more specific than strategic objectives. a) True b) Falsearrow_forwardThe three components of the __________ approach to corporate accounting include financial, environmental, and social performance measures. Multiple Choice a) stakeholder b) triple dimension c) triple bottom line d) triple efficiencyarrow_forward
- Competitors, as internal stakeholders, should be included in the stakeholder management consideration of a company and in its mission statement. a) True b) Falsearrow_forwardAt what level in the organization should the strategic management perspective be emphasized? Multiple Choice a) throughout the organization b) from the bottom up in an organization c) at the top of the organization d) at the middle of the organizationarrow_forwardA good manager can be flexible when it comes to sticking to the original plan; to get good results, the intended strategy has to become the realized strategy. a) True b) Falsearrow_forward
- ________ tend to be quite enduring and seldom change. Multiple Choice a) Strategic objectives b) Vision statements c) Strategic plans d) Mission statementsarrow_forwardThe idea that organizations are not only accountable to stockholders but also to the community-at-large is known as social responsibility. a) True b) Falsearrow_forwardAmong the leaders needed for an effective strategic management process are ________, who, although they have little positional power and formal authority, generate their power through the conviction and clarity of their ideas. Multiple Choice a) executive leaders b) triple bottom line advocates c) internal networkers d) local line leadersarrow_forward
- Operations Research : Applications and AlgorithmsComputer ScienceISBN:9780534380588Author:Wayne L. WinstonPublisher:Brooks ColeC++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage LearningC++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology Ptr