(with-fmt (t) 
  (:esc 
    (loop :repeat 7 
          :do (:fmt (:times #\* 5) 
                 #\Newline))))

(defun calc-counts (total-weight keys &aux results)
  (labels ((calc (left-weight keys-count keys)
             (cond ((= left-weight 0)
                    (push keys-count results))
                   ((and (> left-weight 0) (consp keys))
                    (destructuring-bind (key &rest rest-keys) keys
                      (calc (- left-weight (key-weight key))
                            (add-key keys-count key)
                            keys)
                      (calc left-weight keys-count rest-keys))))))
    (calc total-weight (make-counts keys) keys)
    results))

(defconstant cake&tea-weight 50)
(defconstant    apple-weight 65)
 
(setf (key-weight 'sour)      (+ apple-weight (* 3 cake&tea-weight)))
(setf (key-weight 'half-sour) (+ apple-weight (* 2 cake&tea-weight)))
(setf (key-weight 'sweet)     (+ apple-weight      cake&tea-weight) )
 
(defparameter *fmt*
  "~%Result #~d
  Sour      apples: ~4d
  Half-sour apples: ~4d
  Sweet     apples: ~4d
  Total apples: ~d, cakes: ~d, tea drinks: ~d
")
 
(defun main ()
  (let ((results (calc-counts 1435 '(sour half-sour sweet))))
    (loop :for i :upfrom 1
          :for result :in results :do
          (let* ((sour   (get-key-count result 'sour))
                 (half   (get-key-count result 'half-sour))
                 (sweet  (get-key-count result 'sweet))
                 (apples (+ sour half sweet))
                 (c&t    (+ (* 3 sour) (* 2 half) sweet)))
            (format t *fmt* i sour half sweet apples c&t c&t)))))

Result #1
  Sour      apples:    0
  Half-sour apples:    8
  Sweet     apples:    1
  Total apples: 9, cakes: 17, tea drinks: 17
 
Result #2
  Sour      apples:    1
  Half-sour apples:    6
  Sweet     apples:    2
  Total apples: 9, cakes: 17, tea drinks: 17
 
Result #3
  Sour      apples:    2
  Half-sour apples:    4
  Sweet     apples:    3
  Total apples: 9, cakes: 17, tea drinks: 17
 
Result #4
  Sour      apples:    3
  Half-sour apples:    2
  Sweet     apples:    4
  Total apples: 9, cakes: 17, tea drinks: 17
 
Result #5
  Sour      apples:    4
  Half-sour apples:    0
  Sweet     apples:    5
  Total apples: 9, cakes: 17, tea drinks: 17

;;; Записываю условие в виде списков, как пришло в голову
(defparameter *weights* '((apple 65)
                          (cake 30)
                          (drink 20)))
(defparameter *sets* '((sour (cake 3) (drink 3))
                       (not-so-sour (cake 2) (drink 2))
                       (sweet (cake 1) (drink 1))))
 
(defun apple-set-weight (set)
  "Given a list (apple-type (addon count)*), return the total weight using the data stored in *WEIGHTS*"
  (+ (second (assoc 'apple *weights*))
     ;; хвост списка - закуски; надо просуммировать произведения количества закуски на вес
     (loop :for (item count) :in (rest set)
           :summing (* count (second (assoc item *weights*))))))
 
(defun full-set (set)
  "Given an alist mapping apple types to quantities, return all the addons."
  (loop with h = (make-hash-table :test 'eq)
        for (apple-type apple-count) in set
        do (incf (gethash 'apple h 0) apple-count)
        do (loop for (addon addon-count) in (rest (assoc apple-type *sets*))
                  do (incf (gethash addon h 0) (* addon-count
                                                  apple-count)))
        finally (return
                  (loop for k being the hash-keys in h using (hash-value v)
                        collect (list k v)))))
 
(defparameter *set-weights* (mapcar (lambda (s)
                                      (list (first s)
                                            (apple-set-weight s)))
                                    *sets*)
  "The list of apple types with associated total weights (apple + addons)")
 
#|
Рекурсивное решение. Если дан только один вид яблок, достаточно проверить,
делится ли на него общий вес. Если дано несколько видов яблок, яблокам первого
типа даём значения, начиная от 0, пока укладываемся в общий вес, и пытаемся
решить задачу для остальных типов яблок с остатком веса.
|#
 
(defun solve (apples total-weight)
  "Solve!"
  (cond ((null apples) nil)
        ((null (rest apples))
         (let ((count (/ total-weight (second (assoc (first apples) *set-weights*)))))
           (if (integerp count)
               (list (list (list (first apples)
                                 count)))
               nil)))
        (t (loop with solution
                 with unit-weight = (second (assoc (first apples) *set-weights*))
                 for count upfrom 0
                 for weight from total-weight downto 0 by unit-weight
                 when (setf solution (solve (rest apples) weight))
                 nconc (mapcar (lambda (res)
                                   (cons (list (first apples) count) res))
                                 solution)))))
 
;;; Тестируем в репле
> (solve '(sour not-so-sour sweet) 1435)
(((SOUR 0) (NOT-SO-SOUR 8) (SWEET 1)) ((SOUR 1) (NOT-SO-SOUR 6) (SWEET 2))
 ((SOUR 2) (NOT-SO-SOUR 4) (SWEET 3)) ((SOUR 3) (NOT-SO-SOUR 2) (SWEET 4))
 ((SOUR 4) (NOT-SO-SOUR 0) (SWEET 5)))
> (mapcar (lambda (s) (list s (full-set s))) (solve '(sour not-so-sour sweet) 1435))
((((SOUR 0) (NOT-SO-SOUR 8) (SWEET 1)) ((APPLE 9) (CAKE 17) (DRINK 17)))
 (((SOUR 1) (NOT-SO-SOUR 6) (SWEET 2)) ((APPLE 9) (CAKE 17) (DRINK 17)))
 (((SOUR 2) (NOT-SO-SOUR 4) (SWEET 3)) ((APPLE 9) (CAKE 17) (DRINK 17)))
 (((SOUR 3) (NOT-SO-SOUR 2) (SWEET 4)) ((APPLE 9) (CAKE 17) (DRINK 17)))
 (((SOUR 4) (NOT-SO-SOUR 0) (SWEET 5)) ((APPLE 9) (CAKE 17) (DRINK 17))))