One of the professors of mine asked this question;

Imagine a thief entering a house. In the house, there are infinitely many items
that can have only one of three different weights: 1 kg, 3 kgs, and 5 kgs. All of the items are 
discrete. The thief has a bag capacity of n kgs and strangely, he wants to steal the “smallest 
number of items”.

He wants us to: Show that the greedy choice of taking the largest weight items into the bag first fails to lead to an optimal solution. But I claim that greedy is not failing. In any case taking as much as 5kg item is resulting in minimum number of items which is optimal. Is he wrong? I think greedy is optimal. Is there any case that greedy fails?

By the way, my solution:

public int stealRecursive(int bagCapacity) {
        return stealRecursive(bagCapacity, 0);
    }

private int stealRecursive(int bagCapacity, int numberOfItemsStolen) {

    boolean canSteal5kg = bagCapacity - 5 >= 0;
    boolean canSteal3kg = bagCapacity - 3 >= 0;
    boolean canSteal1kg = bagCapacity - 1 >= 0;

    if (canSteal5kg) {
        return stealRecursive(bagCapacity - 5, numberOfItemsStolen   1);
    }

    if (canSteal3kg) {
        return stealRecursive(bagCapacity - 3, numberOfItemsStolen   1);
    }

    if (canSteal1kg) {
        return stealRecursive(bagCapacity - 1, numberOfItemsStolen   1);
    }

    return numberOfItemsStolen;
}

Some of you stated that putting the code is not pointing anywhere, you are right I just put it to show both my effort and way of thinking. Because whenever I ask a problem without putting my code, I've been warned to show my effort first, due this is not a homework site. That's why I put my code. Sorry for confusing.

CodePudding user response：

First, let's suppose that you have "taken" as many 5k items as possible, so you end up having

m = capacity mod 5

items to be stolen and you have already stolen 5n kilograms.

Cases

m == 0

5n

In this case you have n items and if you have stolen 1k or 3k items, then it would be worse (except for n = 0, in which case it does not make a difference whether you steal 0 items of 5 kilograms, 0 items of 3 kilograms or 0 items of 1 kilogram)

m == 1

5n 1

In this case you have stolen n items of 5 kilograms and you steal an item of 1 kilogram additionally.

In the case of capacity = 6, you can steal 5 1 kilograms or 3 3 kilograms, leading to the same result, but the greater n is, the greater is the advantage of the greedy approach.

m == 2

We have 5n 1 1

in the case of capacity = 7, we have 5 1 1 vs 3 3 1, but in general, greedy is better here as well.

m == 3

5n 3

This is much better than 5n 1 1 1

m == 4

5n 3 1

In the case of 9, we have 5 3 1 vs 3 3 3, but in general, greedy is better

Conclusion

In general, greedy is better, but in some cases there is a tie. The reason is that there is an infinity of items that can be stolen. If there would be finite items of 5, 3, and 1 kilograms, respectively, then we can imagine scenarios like

5k items: 1 3k items: 3 1k items: 0

capacity: 9

Now, if you take the 5k item, then you will end up with a loot of 8, instead of a loot of 9. But we have infinite 5k, 3k and 1k items, so this is not a real scenario.