‘小偷盗取最少物品’问题：贪心算法是否真的失效？

问题背景 #

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”.

教授要求证明：Show that the greedy choice of taking the largest weight items into the bag first fails to lead to an optimal solution

我的疑问 #

但我认为贪心策略不会失效——无论哪种情况，尽可能多拿5kg物品都能得到最少物品数的最优解。难道教授的结论有误？我认为贪心算法是最优的，是否存在能让贪心策略失效的场景？

我的递归实现方案 #

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;
}

关于贴代码的说明 #

有人指出贴代码没有意义，我对此表示认同——贴代码只是为了展示我的思考过程与付出的努力。此前我不贴代码提问时，被提醒需先展示自身努力（毕竟这不是作业网站），因此才贴出代码，抱歉造成困惑。

内容的提问来源于stack exchange，提问作者Baran