Проблема «Украсть минимальное количество предметов как вор»
Один из моих профессоров задал этот вопрос;
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. Но я утверждаю, что жадность не терпит неудачу. В любом случае, взяв предмет весом до 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;
}
Некоторые из вас заявили, что размещение кода никуда не указывает, вы правы, я просто поместил его, чтобы показать как мои усилия, так и образ мышления. Потому что всякий раз, когда я задаю проблему, не помещая свой код, меня предупреждают, чтобы я сначала показал свои усилия, потому что это не сайт с домашними заданиями. Вот почему я поставил свой код. Извините за путаницу.
@cyberbrain Я обновил вопрос, я написал то, что написано в задании.
Кто написал показанный код, представленный как «моё решение»? Вы или профессор? Почему там этот код? Вопрос читается как что-то, что должно быть решено путем рассуждений. Написание кода не похоже на способ «показать, что жадный выбор… не приводит к оптимальному решению». Каким будет поведение кода, который это проверяет? Каково будет поведение кода, который фальсифицирует это? В конце концов, код предоставляет только примеры результатов. Рассуждение, использующее эти результаты для доказательства, отсутствует, не так ли?
Вам нужно найти хотя бы один пример, подтверждающий утверждения профессоров, чтобы доказать это. Вы можете попробовать написать код, который находит решения в алгоритмах выбора, отличных от жадного. Если вы хотите пойти по этому пути, я бы рекомендовал не использовать рекурсию, здесь достаточно целочисленного деления и оператора по модулю. Тем не менее я не могу придумать никакого решения, в котором это утверждение могло бы быть верным, поскольку два из трех размеров могут быть «компенсированы» только большим количеством меньших размеров.
@Yunnosch Я написал код. Я знаю, что размещение кода никуда не указывает, но всякий раз, когда я просто задаю вопрос и не добавляю код, кто-то говорит: «Сначала покажите нам свои усилия, это не веб-сайт hmw». Поэтому ставлю свой код. Извините, если это сбивает с толку
Я действительно понимаю это - и извините за столь быструю реакцию многих пользователей здесь. Однако вам следует перефразировать свой вопрос, чтобы сосредоточиться на логических рассуждениях и объяснить, какой пример предоставляет показанный код и для каких входных данных.
С 1, 3, 5 кг, и если цель состоит в том, чтобы минимизировать количество предметов, то кажется очевидным, что жадный алгоритм (сначала максимальный вес) оптимален. Не всегда так бывает с другим набором весов.
Ответы 1
Во-первых, давайте предположим, что вы «взяли» как можно больше 5 000 предметов, так что в итоге у вас есть
m = capacity mod 5
предметы, которые нужно украсть, и вы уже украли 5n килограммов.
Случаи
м == 0
5н
В этом случае у вас есть n предметов, и если вы украли 1k или 3k предметов, то было бы хуже (за исключением n = 0, в этом случае не имеет значения, украли ли вы 0 предметов по 5 килограммов, 0 предметов по 3 килограмма или 0 штук по 1 килограмму)
м == 1
5н + 1
В этом случае вы украли n вещей весом 5 кг и дополнительно украли вещь весом 1 кг.
В случае емкости = 6 можно украсть 5 + 1 килограмм или 3 + 3 килограмма, что приведет к тому же результату, но чем больше n, тем больше преимущество жадного подхода.
м == 2
У нас есть 5n + 1 + 1
в случае емкости = 7 имеем 5+1+1 против 3+3+1, но в целом и здесь жадность лучше.
м == 3
5н + 3
Это намного лучше, чем 5n+1+1+1
м == 4
5н + 3 + 1
В случае с 9 имеем 5+3+1 против 3+3+3, но в целом лучше жадный
Заключение
В целом лучше жадный, но в некоторых случаях бывает ничья. Причина в том, что существует бесконечное количество предметов, которые можно украсть. Если бы были конечные предметы в 5, 3 и 1 килограмм соответственно, то мы можем представить такие сценарии, как
5к предметов: 1 3к предметов: 3 1к элементов: 0
вместимость: 9
Теперь, если вы возьмете предмет на 5к, то вы получите 8 лут вместо 9. Но у нас есть бесконечные 5к, 3к и 1к предметов, так что это не настоящий сценарий.
Следовательно, жадность оптимальна (просто не однозначно оптимальна). Но задача доказать жадность не оптимальна - значит, что-то не так, возможно, просто в том, как до нас донесли вопрос и его условия.
@undefinedsymbol согласно критериям в вопросе, жадный подход всегда достигает по крайней мере связи с другими подходами. Контрпримера было бы достаточно, чтобы опровергнуть все рассуждения в моем ответе. Но очень похоже, что контрпример найти невозможно. Значит, либо профессор лукавил, задавая ученикам решить неразрешимое, либо произошло недопонимание (или я ошибаюсь, конечно)
Побочный узел: проблема кражи равна проблеме обмена: имея сумму денег, мы должны обменять ее на как можно меньше денег. 1, 3, 5 — это каноническая система монет, что означает, что жадный алгоритм обеспечивает оптимальное решение. arxiv.org/abs/0809.0400
Где-то определен «жадный подход»? Может быть, профессор и вы не имеете в виду один и тот же алгоритм для этого слова ... Для меня «жадный подход» также может заключаться в том, чтобы заполнить мешок 1-килограммовыми элементами, чтобы вы получили наибольшее количество элементов.