greedy algorithms

Question

I am new to algorithms and am currently studying using you-tube video tutorials/lectures and a book, I firstly watch the video and then read the book and finally try a question from the book to make sure I have learned the topic correctly. I am currently up to greedy algorithms and it is very confusing.

Inside the book there are various problems but I am having trouble understanding and answering a particular one.

Firstly it gives the problem which is (I've just copied the text).

there is a set of n objects of sizes {x1; x2;..... xn} and a bin with capacity B. All these are positive integers. Try to find a subset of these objects so that their total size is smaller than or equal to B, but as close to B as possible.

All objects are 1-dimensional. For example, if the objects have sizes 4, 7, 10, 12, 15, and B = 20, then we should choose 4 and 15 with total size 19 (or equivalently, 7 and 12). For each of the following greedy algorithms, show that they are not optimal by creating a counter-example. try to make your examples as bad as you can, where "badness" is measured by the ratio between the optimal and greedy solutions. Thus if the best solution has value 10 and the greedy solution has value 5, then the ratio is 2.

how do I do this for the following?

1) Always choose the object with the largest size so that the total size of this and all other objects already chosen does not exceed B. Repeat this for the remaining objects.

Answer 1

Assume the following instance of the problem:

You have a box of size 2n, one element of size n+1 and the rest are of size n.

It is easy to see that the optimal is 2 elements of size n, while the greedy will get you one element of size n+1.

Since it is true for each n, it actually gives you a desired ratio of at least using this greedy approach 2.

Answer 2

This sounds similar to the 0-1 Knapsack problem where each item has a different size but the same value, which means any one item doesn't have any preference to being placed into the bin other than its size. In your code, you need to examine each item and calculate the maximum total size that results whether or not putting it into the bin without exceeding the capacity of the bin.