0

Есть задача:

Напишите программу, вводящую последовательность целых чисел, которая считает их массами имеющихся в наличии предметов и выясняет, можно ли выбрать из них какое-то количество предметов с суммарным весом 100.

Моя идея решения алгоритмы, заключается в том чтобы суммировать вес всех объектов в последовательности и проверить, что их сумма не меньше 100. Таким образом, думаю, отсечь полноценное выполнение всего алгоритма до начала его выполнения.

Но дальше даже не пойму, так-как очень много итераций по последовательности сделать не вариант, а других вариантов не вижу.

Заранее спасибо за советы и ваши мысли.

3
  • 1
    Ну классическая задача о рюкзаке. Или об одномерном раскрое. Или... да много вариантов. И решения стандартны - ветви и границы, динамика, поиск в ширину и т.п. "Всё украдено ещё до Вас...".
    – Akina
    30 мая 2018 в 18:05
  • @Akina, спасибо за подсказку. 30 мая 2018 в 18:09
  • О! кстати... надо вариант набора, или просто выяснить, можно или нельзя?
    – Akina
    30 мая 2018 в 18:13

2 ответа 2

3

Заведите массив длиной 101. Заполните нулями, только поставьте единицу в A[0].

Теперь для каждого веса P пробегите по массиву
уточнение: в обратном направлении, чтобы не было ложных срабатываний от только что поставленных единиц.

Если в i-м элементе стоит 1, то сумму весов i можно собрать из предыдущих элементов, а значит, вместе с текущим можно собрать i+P, так что поставьте 1 в A[i+P].

Так делать, пока не кончатся элементы или не попадём в сотую ячейку массива.

1
  • Большое спасибо, за Вашу подсказку. 30 мая 2018 в 18:08
0

Ест вариант решения:

1 - отсортировать массив, чтоби было по возрастанию числа.
2 - убираем числа, которие превышают 100 (1,2,45,87,110,205,304) - после отбора чисел - (1,2,45,87)
3 - Используем двоичную систему для "взятия числа из массива".

Пример:

Массив а = {4,25,36,60,75}

Началное двоичное число будет- 00001
Конечное двоичное число будет- 11111

После прибавляем в двоичной системе счисления единицу и считаем сумму на выпавшие ячейки единицы.

Если число, допустим, 11001, то берутся числа {4,25,36,60,75} и суммируются.

Для нашего примера сумма чисел = 100 будут:
10110 - {4,25,36,60,75}
01001 - {4,25,36,60,75}

введите сюда описание изображения

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.