комбинации того, как покупать предметы - PullRequest
Новая
       0

комбинации того, как покупать предметы

2 голосов
/ 06 августа 2011

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

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

Любая помощь будет очень высоко ценится.Спасибо.

1 Ответ

0 голосов
/ 06 августа 2011

Это очень похоже на общий вопрос программирования: «Сколько способов вы можете объединить Y типов монет с Z значениями, чтобы получить X долларов», то есть внести изменения в X долларов с Y типами монет.

Вот общее решение, которое можно перенести на C ++: 

I = list of items SORTED from highest to lowest price
N = number of items bought so far
M = money left
S = money to start

function shop(I, N, M, S):
  if M < 0: return 0 //we bought something illegally! 
  if M == 0:
    //If we have no money, we've bought all we could. 
    //Check our condition that num items N = starting money S
    return 1 if N == S, else 0 
  if I is empty:
    return 0 //no more item combos, no way to buy things.
  else:
    newI = I with first element removed 
    //Every time we want to buy stuff, we have two options: 
    //1. buy something of highest value and subtract money
    //2. Shop ignoring the next highest value item
    return shop(newI, N, M, S) + shop(I, N+1, M-(cost of first item), S)

С X долларами вы начинаете с вызова: 

shop(I, 0, X, X)
...