这是寻找所有加到目标上的组合的一种变体,有两个限制条件。
在本例中,有限的数字集包括25、50、100、200、450、700、1100、1800、2300、2900、3900、5000、5900、7200、8400等。
而函数就是把这些数值加在一起,然后根据我们有多少个数字,再乘以一个数字。
例子:[50, 50, 50] => 300
[50,50,50] => 300。
[100,100] => 300
目标数字包括300、600、900、1500、3000、3600、4400、5600、6400、7600、9600等。
我的直觉是,这不能递归地完成,因为每一步都不知道最终要应用的乘数。
这里有一个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)));
我用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.
我假设查询的数量会很大,这样记忆就会有回报。计数的上限可能会破坏我的代码,因为可能性可能会成倍增长。