英文:
'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
. 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?
fails to lead to an optimal solution
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论