Решение NP-полной проблемы в XKCD

Ответ 1

Точка о NP-полной проблеме заключается не в том, что она сложна в небольшом наборе данных, но в том, что объем работы по ее решению растет со скоростью, большей, чем полином, т.е. нет алгоритма O (n ^ x),

Если временная сложность O (n!), как в (я полагаю), две проблемы, упомянутые выше, то есть в NP.

Ответ 2

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

item(X) :- member(X,[215, 275, 335, 355, 420, 580]).
solution([X|Y], Z) :- item(X), plus(S, X, Z), Z >= 0, solution(Y, S).
solution([], 0).

Решение с swiprolog:

?- solution(X, 1505).

X = [215, 215, 215, 215, 215, 215, 215] ;

X = [215, 355, 355, 580] ;

X = [215, 355, 580, 355] ;

X = [215, 580, 355, 355] ;

X = [355, 215, 355, 580] ;

X = [355, 215, 580, 355] ;

X = [355, 355, 215, 580] ;

X = [355, 355, 580, 215] ;

X = [355, 580, 215, 355] ;

X = [355, 580, 355, 215] ;

X = [580, 215, 355, 355] ;

X = [580, 355, 215, 355] ;

X = [580, 355, 355, 215] ;

No

Ответ 3

Разве это не более элегантно с рекурсией (в Perl)?

#!/usr/bin/perl
use strict;
use warnings;

my @weights  = (2.15, 2.75, 3.35, 3.55, 4.20, 5.80);

my $total = 0;
my @order = ();

iterate($total, @order);

sub iterate
{
    my ($total, @order) = @_;
    foreach my $w (@weights)
    {
        if ($total+$w == 15.05)
        {
            print join (', ', (@order, $w)), "\n";
        }
        if ($total+$w < 15.05)
        {
            iterate($total+$w, (@order, $w));
        }
    }
}

Выход

[email protected]:~$ ./xkcd-knapsack.pl
2.15, 2.15, 2.15, 2.15, 2.15, 2.15, 2.15
2.15, 3.55, 3.55, 5.8
2.15, 3.55, 5.8, 3.55
2.15, 5.8, 3.55, 3.55
3.55, 2.15, 3.55, 5.8
3.55, 2.15, 5.8, 3.55
3.55, 3.55, 2.15, 5.8
3.55, 5.8, 2.15, 3.55
5.8, 2.15, 3.55, 3.55
5.8, 3.55, 2.15, 3.55

Ответ 4

Даже если рюкзак является NP Complete, это особая проблема: обычная динамическая программа для него на самом деле превосходна (http://en.wikipedia.org/wiki/Knapsack_problem)

И если вы сделаете правильный анализ, выясняется, что это O (nW), n - количество элементов, а W - целевое число. Проблема заключается в том, когда вы должны использовать DP по большому W, что когда мы получаем поведение NP. Но по большей части, рюкзак разумно хорошо себя ведет, и вы можете решить действительно большие экземпляры его без проблем. Что касается NP полных проблем, то рюкзак является одним из самых легких.

Ответ 5

Вот решение с помощью constraint.py

>>> from constraint import *
>>> problem = Problem()
>>> menu = {'mixed-fruit': 2.15,
...  'french-fries': 2.75,
...  'side-salad': 3.35,
...  'hot-wings': 3.55,
...  'mozarella-sticks': 4.20,
...  'sampler-plate': 5.80}
>>> for appetizer in menu:
...    problem.addVariable( appetizer, [ menu[appetizer] * i for i in range( 8 )] )
>>> problem.addConstraint(ExactSumConstraint(15.05))
>>> problem.getSolutions()
[{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 5.7999999999999998, 'mixed-fruit': 2.1499999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 7.0999999999999996},
 {'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 0.0, 'mixed-fruit':     15.049999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 0.0}]

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

Ответ 6

Здесь решение с F #:

#light

type Appetizer = { name : string; cost : int }

let menu = [
    {name="fruit"; cost=215}
    {name="fries"; cost=275}
    {name="salad"; cost=335}
    {name="wings"; cost=355}
    {name="moz sticks"; cost=420}
    {name="sampler"; cost=580}
    ] 

// Choose: list<Appetizer> -> list<Appetizer> -> int -> list<list<Appetizer>>
let rec Choose allowedMenu pickedSoFar remainingMoney =
    if remainingMoney = 0 then
        // solved it, return this solution
        [ pickedSoFar ]
    else
        // there more to spend
        [match allowedMenu with
         | [] -> yield! []  // no more items to choose, no solutions this branch
         | item :: rest -> 
            if item.cost <= remainingMoney then
                // if first allowed is within budget, pick it and recurse
                yield! Choose allowedMenu (item :: pickedSoFar) (remainingMoney - item.cost)
            // regardless, also skip ever picking more of that first item and recurse
            yield! Choose rest pickedSoFar remainingMoney]

let solutions = Choose menu [] 1505

printfn "%d solutions:" solutions.Length 
solutions |> List.iter (fun solution ->
    solution |> List.iter (fun item -> printf "%s, " item.name)
    printfn ""
)

(*
2 solutions:
fruit, fruit, fruit, fruit, fruit, fruit, fruit,
sampler, wings, wings, fruit,
*)

Ответ 7

Прочитайте Проблема с рюкзаком.

Ответ 8

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

У меня есть версия PHP, которая выполняет 209 итераций рекурсивного вызова (он делает 2012, если я получаю все перестановки). Вы можете уменьшить свой счет, если до конца цикла вы вытащите элемент, который вы только что отметили.

Я не знаю синтаксиса CF, но это будет примерно так:

        <cfelse>
            <!--- less than 15.50 --->
            <!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
            <cfset found = testCombo(CC, CT, arguments.apps) />
        ------- remove the item from the apps array that was just checked here ------
    </cfif>
</cfloop>

EDIT: Для справки, здесь моя версия PHP:

<?
  function rc($total, $string, $m) {
    global $c;

    $m2 = $m;
    $c++;

    foreach($m as $i=>$p) {
      if ($total-$p == 0) {
        print "$string $i\n";
        return;
      }
      if ($total-$p > 0) {
        rc($total-$p, $string . " " . $i, $m2);
      }
      unset($m2[$i]);
    }
  }

  $c = 0;

  $m = array("mf"=>215, "ff"=>275, "ss"=>335, "hw"=>355, "ms"=>420, "sp"=>580);
  rc(1505, "", $m);
  print $c;
?>

Выход

 mf mf mf mf mf mf mf
 mf hw hw sp
209

ИЗМЕНИТЬ 2:

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

В принципе, каждая рекурсия найдет все комбинации, которые включают текущий элемент поиска (например, первый шаг найдет все, включая, по крайней мере, один смешанный фрукт). Самый простой способ понять это - проследить выполнение, но поскольку это займет много места, я сделаю это, как если бы цель была 6.45.

MF (2.15)
  MF (4.30)
    MF (6.45) *
    FF (7.05) X
    SS (7.65) X
    ...
  [MF removed for depth 2]
  FF (4.90)
    [checking MF now would be redundant since we checked MF/MF/FF previously]
    FF (7.65) X
    ...
  [FF removed for depth 2]
  SS (5.50)
  ...
[MF removed for depth 1]

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

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

Ответ 9

Я бы сделал одно предложение о разработке самого алгоритма (именно так я интерпретировал намерение вашего оригинального вопроса). Вот фрагмент решения, которое я написал:

....

private void findAndReportSolutions(
    int target,  // goal to be achieved
    int balance, // amount of goal remaining
    int index    // menu item to try next
) {
    ++calls;
    if (balance == 0) {
        reportSolution(target);
        return; // no addition to perfect order is possible
    }
    if (index == items.length) {
        ++falls;
        return; // ran out of menu items without finding solution
    }
    final int price = items[index].price;
    if (balance < price) {
        return; // all remaining items cost too much
    }
    int maxCount = balance / price; // max uses for this item
    for (int n = maxCount; 0 <= n; --n) { // loop for this item, recur for others
        ++loops;
        counts[index] = n;
        findAndReportSolutions(
            target, balance - n * price, index + 1
        );
    }
}

public void reportSolutionsFor(int target) {
    counts = new int[items.length];
    calls = loops = falls = 0;
    findAndReportSolutions(target, target, 0);
    ps.printf("%d calls, %d loops, %d falls%n", calls, loops, falls);
}

public static void main(String[] args) {
    MenuItem[] items = {
        new MenuItem("mixed fruit",       215),
        new MenuItem("french fries",      275),
        new MenuItem("side salad",        335),
        new MenuItem("hot wings",         355),
        new MenuItem("mozzarella sticks", 420),
        new MenuItem("sampler plate",     580),
    };
    Solver solver = new Solver(items);
    solver.reportSolutionsFor(1505);
}

...

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

Выход для прогона образца:

7 mixed fruit (1505) = 1505
1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505
348 calls, 347 loops, 79 falls

Я хочу подчеркнуть, что в предлагаемом проекте указывается, что в приведенном выше коде каждый вложенный (рекурсивный) вызов findAndReportSolution(...) имеет дело с количеством точно одного пункта меню, идентифицированного аргументом index. Другими словами, рекурсивная вложенность параллельна поведению встроенного набора вложенных циклов; самый внешний подсчет возможных вариантов использования первого пункта меню, следующий подсчитывает использование второго пункта меню и т.д. (за исключением того, что, конечно, использование рекурсии освобождает код от зависимости от определенного количества элементов меню!)

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

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

Ответ 10

Хм, ты знаешь, что странно. Решение - семь из первого пункта меню.

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

Например,

15.05/2.15 = 7 смешанных фруктов 15.05/2.75 = 5.5 картофель фри.

И затем переходим к простым комбинациям...

15/(2.15 + 2.75) = 3.06122449 смешанные фрукты с картофелем фри.

Я клянусь, что в этот уик-энд я провожу это в местном конусе, когда я заказываю закуски в размере 4,77 доллара США (включая налоги) в 4:30 после закрытия клуба.

Ответ 11

В python.
У меня были некоторые проблемы с "глобальными варами", поэтому я поставил функцию как метод объекта. Он рекурсивный и называет себя 29 раз для вопроса в комиксе, останавливаясь в первом успешном матче

class Solver(object):
    def __init__(self):
        self.solved = False
        self.total = 0
    def solve(s, p, pl, curList = []):
        poss = [i for i in sorted(pl, reverse = True) if i <= p]
        if len(poss) == 0 or s.solved:
            s.total += 1
            return curList
        if abs(poss[0]-p) < 0.00001:
            s.solved = True # Solved it!!!
            s.total += 1
            return curList + [poss[0]]
        ml,md = [], 10**8
        for j in [s.solve(p-i, pl, [i]) for i in poss]:
            if abs(sum(j)-p)<md: ml,md = j, abs(sum(j)-p)
        s.total += 1
        return ml + curList


priceList = [5.8, 4.2, 3.55, 3.35, 2.75, 2.15]
appetizers = ['Sampler Plate', 'Mozzarella Sticks', \
              'Hot wings', 'Side salad', 'French Fries', 'Mixed Fruit']

menu = zip(priceList, appetizers)

sol = Solver()
q = sol.solve(15.05, priceList)
print 'Total time it runned: ', sol.total
print '-'*30
order = [(m, q.count(m[0])) for m in menu if m[0] in q]
for o in order:
    print '%d x %s \t\t\t (%.2f)' % (o[1],o[0][1],o[0][0])

print '-'*30
ts = 'Total: %.2f' % sum(q)
print ' '*(30-len(ts)-1),ts

Вывод:

Total time it runned:  29
------------------------------
1 x Sampler Plate   (5.80)
2 x Hot wings       (3.55)
1 x Mixed Fruit       (2.15)
------------------------------
               Total: 15.05

Ответ 12

На самом деле, я еще немного обновил свой алгоритм. Было несколько правильных комбинаций, которые мне не хватало, и это было связано с тем, что я возвращался, как только стоимость ушла за 15.05 - я не удосужился проверить другие (более дешевые) предметы, которые я мог бы добавить. Вот мой новый алгоритм:

<cffunction name="testCombo" returntype="numeric">
    <cfargument name="currentCombo" type="string" required="true" />
    <cfargument name="currentTotal" type="numeric" required="true" />
    <cfargument name="apps" type="array" required="true" />

    <cfset var a = 0 />
    <cfset var found = false /> 
    <cfset var CC = "" />
    <cfset var CT = 0 />

    <cfset tries = tries + 1 />

    <cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
        <cfset combos = combos + 1 />
        <cfset CC = listAppend(arguments.currentCombo, arguments.apps[a].name) />
        <cfset CT = arguments.currentTotal + arguments.apps[a].cost />
        <cfif CT eq 15.05>
            <!--- print current combo --->
            <cfoutput><strong>#CC# = 15.05</strong></cfoutput><br />
            <cfreturn true />
        <cfelseif CT gt 15.05>
            <!--<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />-->
        <cfelse>
            <!--- less than 15.50 --->
            <!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
            <cfset found = testCombo(CC, CT, arguments.apps) />
        </cfif>
    </cfloop>
    <cfreturn found />
</cffunction>

<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />

<cfset tries = 0 />
<cfset combos = 0 />

<cfoutput>
    <cfloop from="1" to="6" index="b">
        #testCombo(apps[b].name, apps[b].cost, apps)#
    </cfloop>
    <br />
    tries: #tries#<br />
    combos: #combos#
</cfoutput>

Вывод:

Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit = 15.05
Mixed Fruit,hot wings,hot wings,sampler plate = 15.05
Mixed Fruit,hot wings,sampler plate,hot wings = 15.05
Mixed Fruit,sampler plate,hot wings,hot wings = 15.05
false false false hot wings,Mixed Fruit,hot wings,sampler plate = 15.05
hot wings,Mixed Fruit,sampler plate,hot wings = 15.05
hot wings,hot wings,Mixed Fruit,sampler plate = 15.05
hot wings,sampler plate,Mixed Fruit,hot wings = 15.05
false false sampler plate,Mixed Fruit,hot wings,hot wings = 15.05
sampler plate,hot wings,Mixed Fruit,hot wings = 15.05
false
tries: 2014
combos: 12067

Я думаю, что это может иметь все правильные комбинации, но мой вопрос все еще стоит: есть ли лучший алгоритм?

Ответ 13

Изучая @rcar answer, и еще один рефакторинг позже, у меня есть следующее.

Как и во многих вещах, которые я кодирую, я рефакторизую из CFML в CFScript, но код в основном тот же.

Я добавил в его предложение динамическую начальную точку в массиве (вместо того, чтобы передавать массив по значению и изменять его значение для будущих рекурсий), что привело меня к тем же статистическим данным, которые он получает (209 рекурсий, 571 проверка цен на комбинацию (итерации цикла)), а затем улучшилось на этом, предположив, что массив будет сортироваться по стоимости - потому что он - и прерывается, как только мы перейдем к целевой цене. С перерывом мы сокращаем до 209 рекурсий и 376 циклов.

Какие еще улучшения могут быть внесены в алгоритм?

function testCombo(minIndex, currentCombo, currentTotal){
    var a = 0;
    var CC = "";
    var CT = 0;
    var found = false;

    tries += 1;
    for (a=arguments.minIndex; a <= arrayLen(apps); a++){
        combos += 1;
        CC = listAppend(arguments.currentCombo, apps[a].name);
        CT = arguments.currentTotal + apps[a].cost;
        if (CT eq 15.05){
            //print current combo
            WriteOutput("<strong>#CC# = 15.05</strong><br />");
            return(true);
        }else if (CT gt 15.05){
            //since we know the array is sorted by cost (asc),
            //and we've already gone over the price limit,
            //we can ignore anything else in the array
            break; 
        }else{
            //less than 15.50, try adding something else
            found = testCombo(a, CC, CT);
        }
    }
    return(found);
}

mf = {name="mixed fruit", cost=2.15};
ff = {name="french fries", cost=2.75};
ss = {name="side salad", cost=3.35};
hw = {name="hot wings", cost=3.55};
ms = {name="mozarella sticks", cost=4.20};
sp = {name="sampler plate", cost=5.80};
apps = [ mf, ff, ss, hw, ms, sp ];

tries = 0;
combos = 0;

testCombo(1, "", 0);

WriteOutput("<br />tries: #tries#<br />combos: #combos#");

Ответ 14

Здесь параллельная реализация в Clojure. Для расчета (items-with-price 15.05) требуется около 14 комбинированных рекурсий и около 10 проверок возможности. Мне потребовалось около 6 минут, чтобы рассчитать (items-with-price 100) на моем Intel Q9300.

Это дает только первый найденный ответ или nil, если его нет, так как это вызывает все проблемы. Зачем делать больше работы, которую вам сказали сделать?)?

;; np-complete.clj
;; A Clojure solution to XKCD #287 "NP-Complete"
;; By Sam Fredrickson
;;
;; The function "items-with-price" returns a sequence of items whose sum price
;; is equal to the given price, or nil.

(defstruct item :name :price)

(def *items* #{(struct item "Mixed Fruit" 2.15)
               (struct item "French Fries" 2.75)
               (struct item "Side Salad" 3.35)
               (struct item "Hot Wings" 3.55)
               (struct item "Mozzarella Sticks" 4.20)
               (struct item "Sampler Plate" 5.80)})

(defn items-with-price [price]
  (let [check-count (atom 0)
        recur-count (atom 0)
        result  (atom nil)
        checker (agent nil)
        ; gets the total price of a seq of items.
        items-price (fn [items] (apply + (map #(:price %) items)))
        ; checks if the price of the seq of items matches the sought price.
        ; if so, it changes the result atom. if the result atom is already
        ; non-nil, nothing is done.
        check-items (fn [unused items]
                      (swap! check-count inc)
                      (if (and (nil? @result)
                               (= (items-price items) price))
                        (reset! result items)))
        ; lazily generates a list of combinations of the given seq s.
        ; haven't tested well...
        combinations (fn combinations [cur s]
                       (swap! recur-count inc)
                       (if (or (empty? s)
                               (> (items-price cur) price))
                         '()
                         (cons cur
                          (lazy-cat (combinations (cons (first s) cur) s)
                                    (combinations (cons (first s) cur) (rest s))
                                    (combinations cur (rest s))))))]
    ; loops through the combinations of items, checking each one in a thread
    ; pool until there are no more combinations or the result atom is non-nil.
    (loop [items-comb (combinations '() (seq *items*))]
      (if (and (nil? @result)
               (not-empty items-comb))
        (do (send checker check-items (first items-comb))
            (recur (rest items-comb)))))
    (await checker)
    (println "No. of recursions:" @recur-count)
    (println "No. of checks:" @check-count)
    @result))

Ответ 15

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

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

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

public class NPComplete {
    private static final int[] FOOD = { 580, 420, 355, 335, 275, 215 };
    private static int tries;

    public static void main(String[] ignore) {
        tries = 0;
        addFood(1505, "", 0);
        System.out.println("Combinations tried: " + tries);
    }

    private static void addFood(int goal, String result, int index) {
        // If no more food to add, see if this is a solution
        if (index >= FOOD.length) {
            tries++;
            if (goal == 0)
                System.out.println(tries + " tries: " + result.substring(3));
            return;
        }

        // Try all possible quantities of this food
        // If this is the last food item, only try the max quantity
        int qty = goal / FOOD[index];
        do {
            addFood(goal - qty * FOOD[index],
                    result + " + " + qty + " * " + FOOD[index], index + 1);
        } while (index < FOOD.length - 1 && --qty >= 0);
    }
}

Здесь вывод, показывающий два решения:

9 tries: 1 * 580 + 0 * 420 + 2 * 355 + 0 * 335 + 0 * 275 + 1 * 215
88 tries: 0 * 580 + 0 * 420 + 0 * 355 + 0 * 335 + 0 * 275 + 7 * 215
Combinations tried: 88