Найти все комбинации, которые возвращают определенное значение из функции

Question

Это вариант поиска всех комбинаций, которые добавляют к цели, с двумя ограничениями:

• У нас ограниченный набор чисел для работы.
• Числа должен приводить к целевому номеру при подаче в отдельную функцию.

В этом случае ограниченный набор чисел включает 25, 50, 100, 200, 450, 700, 1100, 1800, 2300, 2900, 3900, 5000, 5900, 7200, 8400 и т. Д. c.

И функция состоит в том, чтобы сложить значения вместе, а затем умножить их на число, основанное на количестве чисел:

• Если 1 число, умножить на 1.
• Если 2 числа, умножить на 1,5
• Если 3-6 чисел, умножить на 2
• Если 7- 10 чисел, умножить на 2,5
• Если> 10 чисел, умножить на 3

Примеры:

[50, 50, 50] => 300

[100, 100] => 300

Целевые числа включают 300, 600, 900, 1500, 3000, 3600, 4400, 5600, 6400, 7600, 9600 и др. c.

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

Answer 1

Вот рекурсивный пример в JavaScript, который, кажется, отвечает требованиям:

function getNextM(m, n){
  if (n == 1)
    return 1.5;
  if (n == 2)
    return 2;
  if (n == 6)
    return 2.5;
  if (n == 10)
    return 3;

  return m;
}

function g(A, t, i, sum, m, comb){
  if (sum * m == t)
    return [comb];
    
  if (sum * m > t || i == A.length)
    return [];
    
  let n = comb.length;
    
  let result = g(A, t, i + 1, sum, m, comb);
  
  const max = Math.ceil((t - sum) / A[i]);

  let _comb = comb;
  
  for (let j=1; j<=max; j++){
    _comb = _comb.slice().concat(A[i]);
    sum = sum + A[i];
    m = getNextM(m, n);
    n = n + 1;
    result = result.concat(g(
      A, t, i + 1, sum, m, _comb)); 
  }
  
  return result;
}

function f(A, t){
  return g(A, t, 0, 0, 1, []);
}


var A = [25, 50, 100, 200, 450, 700, 1100, 1800, 2300, 2900, 3900, 5000, 5900, 7200, 8400];

var t = 300;

console.log(JSON.stringify(f(A, t)));

  

Answer 2

Я написал небольшой скрипт в Python3, который может решить эту проблему.

multiply_factor = [0,1,1.5,2,2,2,2,2.5,2.5,2.5,2.5,3]
def get_multiply_factor(x):
    if x< len(multiply_factor):
        return multiply_factor[x]
    else:
        return multiply_factor[-1]


numbers = [25, 50, 100, 200, 450, 700, 1100, 1800, 2300, 2900, 3900, 5000, 5900, 7200, 8400]
count_of_numbers = len(numbers)


# dp[Count_of_Numbers]
dp = [[] for j in range(count_of_numbers+1)]

#Stores multiplying_factor * sum of numbers for each unique Count, See further
sum_found =[set() for j in range(count_of_numbers+1)]

# Stores Results in Unordered_Map for answering Queries
master_record={}

#Initializing Memoization Array
for num in numbers:
    dp[1].append(([num],num*get_multiply_factor(1)))

for count in range(2,count_of_numbers+1):   # Count of Numbers
    for num in numbers:
        for previous_val in dp[count-1]:
            old_factor = get_multiply_factor(count-1)   #Old Factor for Count Of Numbers = count-1
            new_factor = get_multiply_factor(count)     #New Factor for Count Of Numbers = count

            # Multiplying Factor does not change
            if old_factor==new_factor:
                # Scale Current Number and add
                new_sum = num*new_factor+previous_val[1]
            else:
                #Otherwise, We rescale the entire sum
                new_sum = (num+previous_val[1]//old_factor)*new_factor

            # Check if NEW SUM has already been found for this Count of Numbers
            if new_sum not in sum_found[count]:
                # Add to current Count Array
                dp[count].append(([num]+previous_val[0],new_sum))
                # Mark New Sum as Found for Count Of Numbers = count
                sum_found[count].add(new_sum)
                if new_sum not in master_record:
                    # Store Seected Numbers in Master Record for Answering Queries
                    master_record[new_sum] = dp[count][-1][0]



# for i in dp:
#   print(i)
print(master_record[1300])
print(master_record[300])
print(master_record[2300])
print(master_record[7950])
print(master_record[350700.0])

Вывод: -

[100, 100, 450]
[100, 100]
[25, 25, 1100]
[25, 50, 3900]
[1800, 5900, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400, 8400]
[Finished in 0.3s]

My Al go в двух словах.

Iterate over Count[2, Limit], I've considered limit = Number of Elements
    Iterate over List of Numbers
        Iterate over Sums found for previous count.
            Calculate New Sum,
            If it does not exist for current count, update.

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