, we are given a set of n items. Each item weights between 0 and 1....

, we are given a set of n items. Each item weights between 0 and 1. We also have a set of bins (knapsacks). Each bin has a capacity of 1, i.e., total weight in any bin should be less than 1. The problem is to pack the items into as few bins as possible. For example Given items: 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8 Opt Solution: Bin1[0.2, 0.8], Bin2[0.5, 0.4, 0.1], Bin3[0.7, 0.3] Each item must be placed in a bin before the next item can be pro- cessed. This problem is NP-hard. Give an approximation algorithm to solve the bin packing problem. Provide pseudo-code, time complexity analysis and proof of performance ratio.

Solutions

Expert Solution

venereology answered 1 year ago

Next > < Previous

Related Solutions

The data provided below is the same for each item in a set of interrelated items...

The data provided below is the same for each item in a set of interrelated items about the FIFO approach to processes costing. Only the question asked tends to differ from item to item. Together this set of items addresses the same problem. Students are encouraged to work the ENTIRE problem out on scratch paper before responding to any items that relate to this problem. Knuckle makes t-shirts. It uses the FIFO approach to process costing and has a single-stage...

Given a difference equation x[n+2] + 5x[n+1]+6x[n]=n with start values x[0]= 0 and x[1]=0

We are preparing a master production schedule for a given item. For this item the demand...

We are preparing a master production schedule for a given item. For this item the demand forecast and booked orders are as follows: Week 1 2 3 4 5 6 Demand Forecast 60 60 80 80 80 50 Booked Orders 58 63 52 20 4 0 Our Week 0 projected on-hand is 132 units. Lead time for this item is 2 weeks, and the order policy for this item is a fixed quantity of 180 units. When this master schedule...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...

(2) Let Z/nZ be the set of n elements {0, 1, 2, . . . ,...

(2) Let Z/nZ be the set of n elements {0, 1, 2, . . . , n ? 1} with addition and multiplication modulo n. (a) Which element of Z/5Z is the additive identity? Which element is the multiplicative identity? For each nonzero element of Z/5Z, write out its multiplicative inverse. (b) Prove that Z/nZ is a field if and only if n is a prime number. [Hint: first work out why it’s not a field when n isn’t prime....

Question: For each of the following items, determine whether the item would be:

Question: For each of the following items, determine whether the item would be:a. added to the bank balanceb. subtracted from the bank balancec. added to the book balanced. subtracted from the book balance11. Interest revenue earned12. NSF check13. Deposit in transit14. Service charge15. Outstanding check

4. Given Pseudocode: Algorithm3(n): y = 0 for i = 1 to n do y =...

4. Given Pseudocode: Algorithm3(n): y = 0 for i = 1 to n do y = 1 while y < i2 do y=2y return y a. What's the output of Algorithm3(n) as a function of n? b. What's the running time of Algorithm3(n) as a function of n? Represent this as a summation. c. Prove the running time to be O(n log n).

Suppose you have N items with values xi from which we want to sample n items...

Suppose you have N items with values xi from which we want to sample n items with replacement. Each item has its own probability pi of being selected across all times we pick items. What's the estimated variance of the Horvitz-Thompson estimator of T? Let T = > 1, 1=1

Suppose you have N items with values xi from which we want to sample n items...

Suppose you have N items with values xi from which we want to sample n items with replacement. Each item has its own probability pi of being selected across all times we pick items. What's the bias for the following estimator of T: Let T = > 1, 1=1

You are given a set S of n real numbers where for each element x ∈...

You are given a set S of n real numbers where for each element x ∈ S, 1 < | x | < 10. You are also given a black box that returns true if there is some combination (x, y, z) ∈ S such that x · y = z. Say the black box returns only z. Write an O(n log n) algorithm to ﬁnd x and y. In other words, given a set S with n real numbers...

Subjects