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

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

Как с таким количеством вещей я кодирую, я осуществил рефакторинг от 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#");

На самом деле я осуществил рефакторинг свой алгоритм еще немного. Было несколько корректных комбинаций, которые я пропускал, и это было вследствие того, что я возвращался, как только стоимость перешла 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

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

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

....

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 аргумент. Другими словами, рекурсивное вложение параллельно поведению встроенного набора вложенных циклов; наиболее удаленные возможные применения количеств первого пункта меню, следующего в количествах использование второго пункта меню, и т.д. (Кроме, конечно, использование рекурсии освобождает код от зависимости от определенного количества пунктов меню!)

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

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

Читайте на проблема Ранца .

Вот решение с 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's 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,
*)

Вот решение с помощью 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 заказов горячих крыльев или смешанные фрукты порядка 7.

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

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

Разве это не более изящно с рекурсией (в 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));
        }
    }
}

Вывод

marco@unimatrix-01:~$ ./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

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

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

У Вас есть все корректные комбинации теперь, но Вы все еще проверяете намного больше, чем Вам нужно к (как свидетельствуется многими перестановками Ваши шоу результата). Кроме того, Вы опускаете последний объект, который поражает эти 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>

РЕДАКТИРОВАНИЕ: Для ссылки вот моя версия 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]

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

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

Хм, Вы знаете то, что является странным. Решением являются семь из первого объекта в меню.

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

Например,

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

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

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

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

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

Вот параллельная реализация в Clojure. Для вычисления (элементы с ценой 15,05) требуется около 14 рекурсий генерации комбинаций и около 10 проверок возможности. Мне потребовалось около 6 минут, чтобы вычислить (товары по цене 100) на моем Intel Q9300.

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

;; 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))

В 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

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

Кроме того, вы можете использовать математику, чтобы вычислить максимальное количество каждого пищевого продукта для начала каждого раза, чтобы не пробовать комбинации, которые превысили бы цель в $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