可能的“船负载”

Question

您知道过河问题。这是一个排序描述：

从前，三个食人者正在引导三个传教士穿过丛林。他们正在前往最近的传教站的路上。过了一会儿，他们来到了一条宽阔的河边，河里充满了致命的蛇和鱼。没有船就无法过河。幸运的是，经过短暂的搜寻，他们发现了一艘有两支桨的划艇。不幸的是，船太小，无法承载所有人。它几乎不能同时承载两个人。更糟糕的是，由于河水很宽，除了划回去之外，没有办法把船拉回来。 由于传教士不能相信食人者，他们必须制定一个计划，让他们六个人安全过河。问题是，一旦某个地方的食人者比传教士多，这些食人者就会杀死并吃掉传教士。因此，我们的传教士程序员必须制定一项计划，保证河两岸决不存在少数派传教士。然而，食人者们还是可以相信他们会在其他方面进行合作。具体来说，他们不会放弃任何潜在的食物，就像传教士不会放弃任何潜在的皈依者一样。

我的问题是这个问题的一部分。我正在尝试设计一个返回可能的船载列表的函数（例如，如果 Boat_capacity 为 3，则 [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] ）。我有num（传教士或食人者的数量）和船容量作为我的函数的输入。

你如何设计你的函数和算法？

Answer 1

以递归方式思考这个问题，也就是说你想从可能的子问题的角度来思考它。因此，如果您有一艘满载三名乘客的船，那么这显然就像一艘只有一名乘客的船，再加上两名乘客的任意组合。

一艘有两名乘客的船有一名乘客加上“一艘满载一名乘客的船”。

所以你的算法基本上看起来像

to find all combinations of n occupants,
    pick an occupant
    if n = 1 return
    if n > 1 find all combinations of (n-1) occupants.

注意这不是精确解决方案，因为这看起来很像一个家庭作业问题。

Answer 2

或者您可以将其视为生成由两个符号组成的所有长度为 1,2 和 3 的字符串。例如，M 和 C。或者，嗯，零和一！ 0 代表传教士，1 代表食人者。

0 至 1、00 至 11 和 000 至 111。现在您突然想到“如何”生成它们，对吗？

Answer 3

我在Scheme环境下解决了这个问题。也许它不是很快，但它确实有效。

;;; boat-loads : mc_num  boat_capacity --> list of boat_loads 
;;; returns a list of possible (cannibals cannot be more than missionaries)
;;; boat-loads

(define (boat-loads mc bc storage)
 (local 
  ((define isBoatBig (> bc mc))
   (define (both  mc bc storage)
     (cond 
         [(< mc 1) storage]
         [else 
          (both (- mc 1) bc (append storage (list (list mc (- bc mc)))))]))
   (define (single mc bc storage)
    (cond 
      [(= mc 0) storage]
      [else 
       (single (- mc 1) bc (append storage (list (list mc 0) (list 0 mc))))]))
  (define (filt l)
    (local
      ((define (filter-equal l acc)
         (local 
           ((define (filter-equal-inner f  l)
              (cond 
                [(empty? l) (list f)]
                [(equal? f (first l))  (filter-equal-inner (first l) (rest l))]
                [else (append (list (first l))
                              (filter-equal-inner f (rest l)))]))
            (define done (filter-equal-inner (first l) (rest l))))
           (cond 
             [(= 0 acc) done]
             [else (filter-equal done (- acc 1))]))))
       (filter-equal l (length l)))))
  (cond
   [(= bc 0) storage]
   [else 
    (filt (boat-loads mc
                      (- bc 1)
                      (append storage
                              (if isBoatBig 
                                  (filter (lambda (x)
                                            (if (>= (first x) (second x))
                                                true false))
                                          (append (both mc bc empty)
                                                  (single mc bc empty)))
                                  (filter (lambda (x)
                                            (if (>= (first x) (second x))
                                                true false))
                                          (append (both bc bc empty)
                                                  (single bc bc empty)))))))])))