你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
function solve(n){
let DP = [];
DP[0] = DP[1] = DP[2] = 1;
DP[3] = 2;
for (let i = 4; i <= n; i++) {
DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
}
return DP[n]
}
console.log(solve(5))
这是JS的一个动态解决方案,告诉任何人有多少种方法可以得到一定的总和。如果考虑到时间和空间的复杂性,这可能是正确的解决方案。
其他回答
import java.util.*;
public class Main{
int recursionDepth = 0;
private int[][] memo;
public static void main(String []args){
int[] nums = new int[] {5,2,4,3,1};
int N = nums.length;
Main main = new Main();
main.memo = new int[N+1][N+1];
main._findCombo(0, N-1,nums, 8, 0, new LinkedList() );
System.out.println(main.recursionDepth);
}
private void _findCombo(
int from,
int to,
int[] nums,
int targetSum,
int currentSum,
LinkedList<Integer> list){
if(memo[from][to] != 0) {
currentSum = currentSum + memo[from][to];
}
if(currentSum > targetSum) {
return;
}
if(currentSum == targetSum) {
System.out.println("Found - " +list);
return;
}
recursionDepth++;
for(int i= from ; i <= to; i++){
list.add(nums[i]);
memo[from][i] = currentSum + nums[i];
_findCombo(i+1, to,nums, targetSum, memo[from][i], list);
list.removeLast();
}
}
}
c#版本的@msalvadores代码的答案
void Main()
{
int[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new List<int>(numbers.ToList()),target);
}
static void sum_up_recursive(List<int> numbers, int target, List<int> part)
{
int s = 0;
foreach (int x in part)
{
s += x;
}
if (s == target)
{
Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target);
}
if (s >= target)
{
return;
}
for (int i = 0;i < numbers.Count;i++)
{
var remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count;j++)
{
remaining.Add(numbers[j]);
}
var part_rec = new List<int>(part);
part_rec.Add(n);
sum_up_recursive(remaining,target,part_rec);
}
}
static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers,target,new List<int>());
}
这类似于硬币更换问题
public class CoinCount
{
public static void main(String[] args)
{
int[] coins={1,4,6,2,3,5};
int count=0;
for (int i=0;i<coins.length;i++)
{
count=count+Count(9,coins,i,0);
}
System.out.println(count);
}
public static int Count(int Sum,int[] coins,int index,int curSum)
{
int count=0;
if (index>=coins.length)
return 0;
int sumNow=curSum+coins[index];
if (sumNow>Sum)
return 0;
if (sumNow==Sum)
return 1;
for (int i= index+1;i<coins.length;i++)
count+=Count(Sum,coins,i,sumNow);
return count;
}
}
用excel找到组合(相当容易)。 (你的电脑不能太慢)
去这个网站 进入“Sum to Target”页面 下载“Sum to Target”excel文件。 按照网站页面上的说明操作。
希望这能有所帮助。
Thank you.. ephemient
我已经将上述逻辑从python转换为php..
<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;
print_r(bestsum($data,$maxsum)); //function call
function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array(); //base case
foreach($data as $group)
{
$new_res = $res; //copy res
foreach($group as $ele)
{
for($i=0;$i<($maxsum-$ele+1);$i++)
{
if($res[$i] != 0)
{
$ele_index = $i+$ele;
$new_res[$ele_index] = $res[$i];
$new_res[$ele_index][] = $ele;
}
}
}
$res = $new_res;
}
for($i=$maxsum;$i>0;$i--)
{
if($res[$i]!=0)
{
return $res[$i];
break;
}
}
return array();
}
?>