Некоторый фон. Вышеупомянутая проблема - проблема ранца с ограничениями. Наиболее эффективное решение проблемы ранца с или без ограничений может быть решено за псевдополиномиальное время, все еще NP-Hard. Для некоторых вариантов см. Https://en.wikipedia.org/wiki/Knapsack_problem#Definition . Первое ограничение в этом варианте заключается в том, что стоимость предметов (шариков), помещаемых в рюкзак (мусорные ведра), не имеет значения. Проблема тогда ограничена количеством времени, которое требуется, чтобы поместить предметы в рюкзак. Первоначальная задача требует, чтобы самые ценные предметы были размещены в кратчайшие сроки. Другое ограничение этой версии - весовые коэффициенты и все остальные аргументы являются целыми числами. И ограничение интереса в том, что весыw j + 1 jвесJразделить для всех . Примечание: проблема дробного ранца может быть решена за полиномиальное время, но не дает наиболее практичных решений исходной задачи. В этой задаче используются целые числа, которые делятся равномерно (без рациональных решений). Может быть, посмотрите, в чем же проблема с рюкзаком? ,весJ + 1J
Главный вопрос, возможно, должен заключаться в том, является ли эта проблема все еще NP- когда не ограничен полиномом, соответствующим , поскольку задача менее сложна (в P), когда она ограничена? Причина, по которой я говорю, заключается в том, что проблема может показано, что он находится в P, когда ограничен, и NP-Hard, когда не обязательно делит i w j w j w j + 1весJявесJвесJвесJ + 1равномерно (веса просто случайные), все ограничения ограничивают сложность этой задачи этими двумя условиями. Эти условия (1. случайная задача о ранце с весом без ограничения по стоимости предмета и 2. задача о ранце с делимым весом без ограничения по стоимости предмета) сводят на нет друг друга с точки зрения уменьшения сложности, так как коэффициенты весов сами могут быть случайными ( особенно когда он неограничен), что накладывает экспоненциальные временные вычисления (это будет показано в примере ниже). Кроме того, поскольку делит , экспоненциально увеличивается для каждогоw j + 1 w j j w jвесJвесJ + 1весJJ, Это связано с тем, что вместо использования случайных взвешенных предметов (шаров, удельный вес которых может быть ограничен единичным весом менее 100, или 50, или даже 10), вместо этого ограничение приводит к тому, что сложность времени зависит от количества цифр , так же, как пробное деление, которое является экспоненциальным.весJ
Так что да, вышеуказанная целочисленная программа остается NP-сложной, даже когда делит на все . w j + 1 jвесJвесJ + 1J И это легко заметить.
Пример 1: пустьи- степени двойки. Из-за константы два вся проблема решается за квадратичное время, как показывает ваш пример. Веса не случайны, и поэтому расчет решается эффективно.w pn = 1весп
Пример 2: пустьопределяется как, где- простое число, соответствующее, такое, что. Это применимо, так какделитдля всех w j ∗ p p j p = 2 , j = 1 : p = 3 , j = 2 , p = 5 , j = 3весJ + 1весJ∗ рпJw j w j + 1 j w j j 1 ,p=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,Jwjwj+1j . Мы получаем, что каждый является произведением всех простых чисел до . Значения удельных весов увеличивают как таковые: . Так как есть граница ( ~wjjp j j l o g ( j )1,2,6,30,210,2310,30030,...pjjlog(j)через теорему о простых числах), поскольку все факторы являются простыми числами, мы получаем сложность NP-Intermediate.
Пример 3: пустьопределяется как, где- произвольно выбранное простое число от двух до бесконечности, соответствующее. Это применимо к этой проблеме, так какделитдля всех. Мы получаем первые 5 факторов (случайным образом падая с двух до бесконечности), как. Мы видим, что даже на 5-м шаре вес имеет одиннадцать цифр. К счастью, пятым частным было два, а не простое число порядкаили больше. w j ∗ R pwj+1wj∗Rp j w j w j + 1 j 101 , 2657 , 7 , 3169 , 2 10 100Rpjwjwj+1j101,2657,7,3169,210100
выше третий пример - это то, что происходит, когда не ограничен (случайные веса) полиномом, соответствующим . Сложность времени экспоненциальная, NP-Hard. Для некоторой перспективы просто сложите все веса, посмотрите, подходят ли они. Но не существует решения, позволяющего решить его значительно быстрее, сделав весовые коэффициенты делимыми, чем попытка каждого подмножества проверить, работает ли он. После нескольких дюжин шаров, вы все еще входите в царство даже триллионов подмножеств или триллионов цифр. яwji