Возможная комбинация проблемы рюкзака и? - PullRequest
Новая
       15

Возможная комбинация проблемы рюкзака и?

3 голосов
/ 23 апреля 2009

Хорошо, краткий обзор

Я изучил проблему с рюкзаком

http://en.wikipedia.org/wiki/Knapsack_problem

и я знаю, что это то, что мне нужно для моего проекта, но сложной частью моего проекта было бы то, что мне нужно несколько мешков внутри основного мешка.

Большой рюкзак, в котором хранятся все «сумки», может нести только х количество «сумок» (скажем, 9 для примера). Каждая сумка имеет разные значения;

  • Вес
  • Стоимость
  • размер
  • Емкость

и так далее, все эти значения являются целыми числами. Допустим, от 0 до 100.

Внутреннему пакету также будет назначен тип, и во внешнем пакете может быть только один из этого типа, хотя для ввода программы будет задано несколько значений одного типа.

Мне нужно назначить максимальный вес, который может вместить основная сумка, а все остальные свойства более мелких сумок необходимо сгруппировать по взвешенным значениям.

* 1 028 * Пример * +1029 *

Наружная сумка:

  • Может вместить 9 меньших сумок
  • Вес не более 98 [Дай или возьми 5 с каждой стороны]
  • Должен содержать по одному каждому типу. Может содержать только по одному типу за раз.

Внутренние сумки:

  • Стоимость, взвешенная на 100%
  • Размер, взвешенный на 67%
  • Емкость, взвешенная на 44%

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

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

Я буду программировать его на Java или C #. Я хотел бы запрограммировать его на PHP, но я боюсь, что алгоритм будет очень неэффективным для веб-серверов.

Спасибо за любую помощь, которую вы можете оказать

-Zack

Ответы [ 2 ]

2 голосов
/ 23 апреля 2009

Хорошо, ну, рюкзак - NP-жесткий, так что я уверен, что это будет и NP-hard (если бы не было, вы могли бы решить рюкзак, выполнив это только с одной внешней сумкой.) оптимальное решение, вы, вероятно, сможете сделать не лучше, чем поиск по всем комбинациям. Таким образом, план программы, которую вы хотите, будет выглядеть как 

 for each possible combination
 do
   if current combination is better than best previous
      save current combination as best so far
   fi
 od

и время выполнения будет экспоненциальным. Это звучит, однако, как будто вы могли бы найти близкое решение с динамическим программированием .

0 голосов
/ 24 апреля 2009

Рассмотрите возможность использования Пролог для логического программирования. Есть несколько реализаций этого, включая P # на моно (.NET). Есть немного кривой обучения, но как только вы к этому привыкнете, это в значительной степени само по себе для решения подобных задач.

Надеюсь, это поможет. Ура!

ссылка на P #

...