достижение цели номер

Question

Я новичок, поэтому, если этот вопрос звучит глупо/неясно или очень легко, пожалуйста, несите меня.

Как добавить список чисел для достижения целевого номера или как можно ближе? Например, вот список чисел: (2,3,4,7,20,25), goal = 105. Результат должен быть следующим: (25,25,25,25,3,2). Порядок заданных чисел имеет значение; всегда начинайте с самого большого числа в списке и добавляйте их, чтобы приблизиться к данному значению, поэтому он будет выбирать следующую цифру для проверки. результатом может быть также (20, 20, 20, 20, 25), что в данном случае является неправильным, поскольку оно не соответствует порядку номеров. Алгоритм перескакивает только на следующий номер, если он может ногами в противном случае не может прыгать.

Best M

Answer 1

Я хотел бы взять динамического программирования подход:

def fewest_items_closest_sum_with_repetition(items, goal): 
    """ 
    Given an array of items 
     where each item is 0 < item <= goal 
     and each item can be used 0 to many times 

    Find the highest achievable sum <= goal 

    Return any shortest (fewest items) sequence 
     which adds to that sum. 
    """ 
    assert goal >= 0, "Invalid goal" 
    # remove any duplicate or invalid items 
    items = set(item for item in items if 0 < item <= goal) 
    # sort descending (work with largest values first) 
    items = sorted(items, reverse=True) 

    # start with the no-item sequence 
    best = {0: []} 
    active = {0: []} 
    # while we have further seeds to work from 
    while active: 
     nactive = {} 
     for item in items: 
      for total, seq in active.items(): 
       # find next achievable sum 
       ntotal = total + item 
       # if it is a valid subgoal and has not already been found 
       if (ntotal <= goal and ntotal not in best): 
        # save it 
        best[ntotal] = nactive[ntotal] = [item] + seq 
        if ntotal == goal: 
         # best possible solution has been found! 
         break 
     active = nactive 

    # return the best solution found 
    return best[max(best)] 

, который затем проходит как

>>> fewest_items_closest_sum_with_repetition([2,3,4,7,20,25], 105) 
[25, 20, 20, 20, 20] 

>>> fewest_items_closest_sum_with_repetition((40,79), 80) 
[40, 40] 

Answer 2

l=(2,3,4,7,20,25) 
goal = 105 

a=max(l) 
b=0 
res=[] 
while b<=goal-24: 
    b+=a 
    t=goal-b 
    res.append(a) 
    g=0 
    for x in l: 
     g+=x 
     if g==t: 
      res.append(x) 
      res.append(g-x) 
      break 

print (res) 

Выход:

>>> 
[25, 25, 25, 25, 3, 2] 
>>> 

Я нашел это решение, однако, на самом деле раздражает меня :-)! Tricky part while b<=goal-24:, другие коды являются базовыми Python.

Answer 3

Правильно ли это? У меня нет времени проверять прямо сейчас.

def solution(numbers, goal): 
    curr = 0 
    numbers = sorted(numbers) 
    while curr < goal: 
     if not numbers: break 
     n = numbers.pop() 
     while n + curr <= goal: 
      yield n 
      curr += n 

list(solution([2,3,4,7,20,25], 105)) 

Результаты:

[25, 25, 25, 25, 4] 

Answer 4

Если скорость не является проблемой, вот в конечном счете, правильный ответ:

import itertools 

def change_maker(coins, amount): 
    for r in range(amount//max(coins), amount//min(coins)+1): 
     possibilities = (combo for combo in itertools.combinations_with_replacement(coins, r) if sum(combo) == amount) 
     try: 
      result = next(possibilities) 
     except StopIteration: 
      # no solution with current r 
      continue 
     else: 
      return result 

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

DEMO:

>>> coins = (2, 3, 4, 7, 20, 25) 
>>> goals = 105 
>>> print(change_maker(coins, goal)) 
[20, 20, 20, 20, 25]