“Steal minimum number of items as a thief” 问题

huangapple go评论70阅读模式
英文:

'Steal minimum number of items as a thief' problem

问题

以下是翻译好的部分:

有一位我的教授提出了这个问题:

"假设一个小偷进入了一座房子。在这个房子里,有无穷多个物品,它们只能有三种不同的重量:1公斤、3公斤和5公斤。所有的物品都是离散的。小偷的袋子容量为n公斤,奇怪的是,他想要偷取“物品数量最少的物品”。

他要我们:“证明贪婪地首先将最重的物品放入袋子中不会导致最优解”。但我认为贪婪是不会失败的。无论如何,拿走5公斤的物品会导致物品数量最少,这是最优解。他错了吗?我认为贪婪是最优的。有没有贪婪失败的情况?

顺便说一下,我的解决方案:

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

一些人提到,放置代码没有指向任何地方,你们是对的,我只是为了展示我的努力和思考方式才放置的。因为每当我在没有放置我的代码的情况下提出问题时,都会被警告要先展示我的努力,因为这不是一个作业网站。这就是为什么我放置了我的代码。对于造成的困惑,我感到抱歉。

英文:

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.

答案1

得分: 3

首先,让我们假设您已经尽可能多地“拿走”了5千克的物品,这样您最终会有

m = 容量 mod 5

要偷取的物品,并且您已经偷取了5n千克。

情况

m == 0

5n

在这种情况下,您有n个物品,如果您偷取了1千克或3千克的物品,那么情况会更糟(除非n = 0,在这种情况下,无论您是偷取5千克的物品、3千克的物品还是1千克的物品,都没有区别)

m == 1

5n + 1

在这种情况下,您已经偷取了n个5千克的物品,还偷取了1千克的物品。

在容量等于6的情况下,您可以偷取5 + 1千克,或者3 + 3千克,结果相同,但n越大,贪婪方法的优势就越大。

m == 2

我们有5n + 1 + 1

在容量等于7的情况下,我们有5 + 1 + 1 vs 3 + 3 + 1,但总的来说,贪婪方法在这里也更好。

m == 3

5n + 3

这比5n + 1 + 1 + 1要好得多。

m == 4

5n + 3 + 1

在9的情况下,我们有5 + 3 + 1 vs 3 + 3 + 3,但总的来说,贪婪方法更好

结论

总的来说,贪婪方法更好,但在某些情况下会出现并列。原因是可以偷取无限多个物品。如果存在5、3和1千克的有限物品,那么我们可以想象出以下情景:

5千克物品:1
3千克物品:3
1千克物品:0

容量:9

现在,如果您拿走5千克的物品,您最终将得到8千克的战利品,而不是9千克的战利品。但我们有无限多的5千克、3千克和1千克的物品,因此这不是一个真实的情景。

英文:

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.

huangapple
  • 本文由 发表于 2023年1月9日 01:37:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/75049989.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定