Design an algorithm that implements the best-fit heuristic

Assignment Help Basic Computer Science

Reference no: EM131361962

In the bin-packing problem, we are given n metal objects, each weighing between zero and one kilogram. Our goal is to find the smallest number of bins that will hold the n objects, with each bin holding one kilogram at most.

• The best-fit heuristic for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted.. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the n weights w₁, w₂, ..., w_n and outputting the number of bins used) in O(n log n) time.

• Repeat the above using the worst-fit heuristic, where we put the next object in the partially filled bin with the largest amount of extra room after the object is inserted.

Reference no: EM131361962

Questions Cloud

The value of critical thinking : Give your opinion on whether being an effective critical thinker makes decision making easier or more challenging. Justify your response - Explain the fundamental ways in which effectively applying critical thinking concepts has helped you to become..

Evaluate the effectiveness of the organizations hr policies : Imagine that you are the Director of the HR Department at your current organization or an organization with which you are familiar. You are responsible for delegating duties to your team for the selection, development, and management of both the n..

Develop an action plan to share with the hospital staff : Develop an action plan to share with the hospital staff and CDC local office to address and contain the outbreak in an effective and efficient manner at the hospital

Blood pressure measured with the person sitting upright : a. What are the two separate fluid systems when a cuff is used measure a person's blood pressure? Are the two systems connected, and if so, how? b. Using a cuff around the upper arm, why is blood pressure measured with the person sitting upright?

Design an algorithm that implements the best-fit heuristic : In the bin-packing problem, we are given n metal objects, each weighing between zero and one kilogram. Our goal is to find the smallest number of bins that will hold the n objects, with each bin holding one kilogram at most.

Examine the pros from the perspective of crestview hospital : Examine the pros and cons from the perspective of Crestview Hospital of the placement of its new billboard directly adjacent to Briarwood Medical Center.

Complete a research-driven formal business report : Complete a 1,000- to 1,250-word Research-Driven Formal Business Report that proposes a change to the workplace or proposes a new initiative using the components of ethical business communication.

Description of the big bang : Q.1. Give a brief (just a few lines) description of the big bang. What does it predict? What doesn't it predict? A little history would be nice here. Please cite any references you use.

What are the various leading companies in the industry : Are there any new entrants in the marketplace? Is this industry heavily regulated? What are the various leading companies in the industry? How long have they been in the market?

User Account

All Pages