goabove1970
BAN USERI found 2 solutions, a simple for multiples of 2 elements and recursive approach involving multiples of all elements.
The first and the simplest approach is to build a table of all possible multiplies and sum them with each other, this would work with A={6,9,20} and T=47 but is limited to only multiples of 2 elements. This method will fail with A={7411, 9461, 20161, 1901, 1531, 281} and T=27751.
The second approach would recursively go through all multiples of all elements (without using multiples of the same elements) and so it may engage a multiple element in A. This approach will work if the target T comprises of multiples of 3 and more elements of A.
static void Main(string[] args)
{
int[] arr = new int[6]{7411, 9461, 20161, 1901, 1531, 281};
var target = 27751;
Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
// testing with big primes
Console.WriteLine("Simple:");
FindComboSimple(arr, target); // 2 primes can not produce 27751
Console.WriteLine("Recursive:");
FindComboRec(arr, target); // 3 or more primes can prodice 27751
//testing given example
arr = new int[3] { 6,9,20 };
target = 47;
Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
Console.WriteLine("Simple:");
FindComboSimple(arr, 47);
Console.WriteLine("Recursive:");
FindComboRec(arr, 47);
Console.ReadLine();
}
public static void FindComboSimple(int[] ar, int target)
{
var mults = new int[ar.Length][];
// calculating all possible multiplies which are less then target
for (int i =0; i < ar.Length; i++)
{
if (ar[i] == 0)
continue;
var maxKoef = target / ar[i];
mults[i] = new int[maxKoef - 1];
for (var k = 0; k < maxKoef - 1; k ++)
mults[i][k] = ar[i] * (k + 1);
}
// adding every possible mults with each other to find target
for(var i = 0; i < mults.Length; i++)
{
for (var j = 0; j < mults[i].Length; j++)
{
for (var ii = i; ii < mults.Length; ii ++)
{
if (ii == i)
continue;
for (var jj = 0; jj < mults[ii].Length; jj ++)
{
if (mults[i][j] + mults[ii][jj] == target)
{
Console.WriteLine($"{target} = {mults[i][0]}*{j + 1} + {mults[ii][0]}*{jj + 1}");
return;
}
}
}
}
}
}
public static bool FindComboRec(int[] arr, int target, int ipos = -1, int val = 0, string currentExpr = "")
{
for(var i = ipos + 1; i < arr.Length; i++)
{
if (arr[i] == 0)
continue;
for(var j = 0; j < target / arr[i] ; j ++)
{
var currentValue = arr[i] * j + val;
if (currentValue == target)
{
Console.WriteLine($"{target} = {arr[i]}*{j}{currentExpr}");
return true;
}
else
{
var expr = (j != 0 ? (currentExpr + $" + {arr[i]}*{j}" ):currentExpr);
if (FindComboRec(arr, target, i, currentValue, expr))
return true;
}
}
}
return false;
}
Output:
Values: 7411, 9461, 20161, 1901, 1531, 281; Target = 27751
Simple:
Recursive:
27751 = 281*5 + 1901*5 + 1531*11
Values: 6, 9, 20; Target = 47
Simple:
47 = 9*3 + 20*1
Recursive:
47 = 20*1 + 9*3
Recursively searching for max total of sums in the remaining sub-array for each sum in the present array.
Output:
- goabove1970 March 20, 2017Positions: (0, 3, 5), sum = 23
Sum #1: (1, 2)
Sum #2: (2, 6)
Sum #3: (7, 5)