找出所有从函数中返回一个特定值的组合。

问题描述 投票:0回答:1

这是寻找所有加到目标上的组合的一种变体,有两个限制条件。

  • 我们有一组有限的数字可以使用。
  • 当这些数字被输入到一个单独的函数中时,其结果必须是目标数字。

在本例中,有限的数字集包括25、50、100、200、450、700、1100、1800、2300、2900、3900、5000、5900、7200、8400等。

而函数就是把这些数值加在一起,然后根据我们有多少个数字,再乘以一个数字。

  • 如果是一个数字,就乘以1.
  • 如果是2个数,就乘以1.5。
  • 如果是3-6个数,就乘以2
  • 如果是7-10个数字,则乘以2.5。
  • 如果是10个数字,则乘以3。

例子:[50, 50, 50] => 300

[50,50,50] => 300。

[100,100] => 300

目标数字包括300、600、900、1500、3000、3600、4400、5600、6400、7600、9600等。

我的直觉是,这不能递归地完成,因为每一步都不知道最终要应用的乘数。

algorithm
1个回答
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)));

  

0
投票

我用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]

我的Algo简而言之。

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.

我假设查询的数量会很大,这样记忆就会有回报。计数的上限可能会破坏我的代码,因为可能性可能会成倍增长。

© www.soinside.com 2019 - 2024. All rights reserved.