Calculate all possibilities to get N using values from a given set [duplicate]

Question

So here is the problem:

Given input = [100 80 66 25 4 2 1], I need to find the best combination to give me 50.

Looking at this, the best would be 25+25 = 50, so I need 2 elements from the array.

Other combinations include 25+4+4+4+4+4+4+1 and 25+4+4+4+4+4+2+2+1.. etc etc

I need to find all the possibilities which gives me the sum on a value I want.

EDIT: As well as the best possibility (one with least number of terms)

Here is what I have done thus far: First build a new array (simple for loop which cycles through all elements and stores in a new temp array), check for all elements higher than my array (so for input 50, the elements 100,80,66 are higher, so discard them and then my new array is [25 4 2 1]). Then, from this, I need to check combinations.

The first thing I do is a simple if statement checking if any array elements EXACTLY match the number I want. So if I want 50, I check if 50 is in the array, if not, I need to find combinations.

My problem is, I'm not entirely sure how to find every single combination. I have been struggling trying to come up with an algorithm for a while but I always just end up getting stumped.

Any help/tips would be much appreciated.

PS - we can assume the array is always sorted in order from LARGEST to SMALLEST value.

Answer 1

This is the kind of problem that dynamic programming is meant to solve.

Create an array with with indices, 1 to 50. Set each entry to -1. For each element that is in your input array, set that element in the array to 0. Then, for each integer n = 2 to 50, find all possible ways to sum to n. The number of sums required is the minimum of the two addends plus 1. At the end, get the element at index 50.

Answer 2

Edit: Due to a misinterpretation of the question, I first answered with an efficient way to calculate the number of possibilities (instead of the possibilities themself) to get N using values from a given set. That solution can be found at the bottom of this post as a reference for other people, but first I'll give a proper answer to your questions.

---

Generate all possibilities, count them and give the shortest one

When generating a solution, you consider each element from the input array and ask yourself "should I use this in my solution or not?". Since we don't know the answer until after the calculation, we'll just have to try out both using it and not using it, as can be seen in the recursion step in the code below.

Now, to avoid duplicates and misses, we need to be a bit careful with the parameters for the recursive call. If we use the current element, we should also allow it to be used in the next step, because the element may be used as many times as possible. Therefore, the first parameter in this recursive call is i. However, if we decide to not use the element, we should not allow it to be used in the next step, because that would be a duplicate of the current step. Therefore, the first parameter in this recursive call is i+1.

I added an optional bound (from "branch and bound") to the algorithm, that will stop expanding the current partial solution if it is known that this solution will never be shorter then the shortest solution found so far.

package otherproblems;

import java.util.Deque;
import java.util.LinkedList;

public class GeneratePossibilities
{
    // Input
    private static int n = 50;
    // If the input array is sorted ascending, the shortest solution is
    // likely to be found somewhere at the end.
    // If the input array is sorted descending, the shortest solution is
    // likely to be found somewhere in the beginning.
    private static int[] input = {100, 80, 66, 25, 4, 2, 1};

    // Shortest possibility
    private static Deque<Integer> shortest;
    // Number of possibilities
    private static int numberOfPossibilities;

    public static void main(String[] args)
    {
        calculate(0, n, new LinkedList<Integer>());
        System.out.println("\nAbove you can see all " + numberOfPossibilities +
            " possible solutions,\nbut this one's the shortest: " + shortest);
    }

    public static void calculate(int i, int left, Deque<Integer> partialSolution)
    {
        // If there's nothing left, we reached our target
        if (left == 0)
        {
            System.out.println(partialSolution);
            if (shortest == null || partialSolution.size() < shortest.size())
                shortest = new LinkedList<Integer>(partialSolution);
            numberOfPossibilities++;
            return;
        }
        // If we overshot our target, by definition we didn't reach it
        // Note that this could also be checked before making the
        // recursive call, but IMHO this gives a cleaner recursion step.
        if (left < 0)
            return;
        // If there are no values remaining, we didn't reach our target
        if (i == input.length)
            return;

        // Uncomment the next two lines if you don't want to keep generating
        // possibilities when you know it can never be a better solution then
        // the one you have now.
//      if (shortest != null && partialSolution.size() >= shortest.size())
//          return;

        // Pick value i. Note that we are allowed to pick it again,
        // so the argument to calculate(...) is i, not i+1.
        partialSolution.addLast(input[i]);
        calculate(i, left-input[i], partialSolution);
        // Don't pick value i. Note that we are not allowed to pick it after
        // all, so the argument to calculate(...) is i+1, not i.
        partialSolution.removeLast();
        calculate(i+1, left, partialSolution);
    }

}

---

Calculate the number of possibilities efficiently

This is a nice example of dynamic programming. What you need to do is figure out how many possibilities there are to form the number x, using value y as the last addition and using only values smaller than or equal to y. This gives you a recursive formula that you can easily translate to a solution using dynamic programming. I'm not quite sure how to write down the mathematics here, but since you weren't interested in them anyway, here's the code to solve your question :)

import java.util.Arrays;

public class Possibilities
{
    public static void main(String[] args)
    {
        // Input
        int[] input = {100, 80, 66, 25, 4, 2, 1};
        int n = 50;

        // Prepare input
        Arrays.sort(input);

        // Allocate storage space
        long[][] m = new long[n+1][input.length];

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < input.length; j++)
            {
                // input[j] cannot be the last value used to compose i
                if (i < input[j])
                    m[i][j] = 0;
                // If input[j] is the last value used to compose i,
                // it must be the only value used in the composition.
                else if (i == input[j])
                    m[i][j] = 1;
                // If input[j] is the last value used to compose i,
                // we need to know the number of possibilities in which
                // i - input[j] can be composed, which is the sum of all
                // entries in column m[i-input[j]].
                // However, to avoid counting duplicates, we only take
                // combinations that are composed of values equal or smaller
                // to input[j].
                else
                    for (int k = 0; k <= j; k++)
                        m[i][j] += m[i-input[j]][k];
            }

        // Nice output of intermediate values:
        int digits = 3;
        System.out.printf(" %"+digits+"s", "");
        for (int i = 1; i <= n; i++)
            System.out.printf(" %"+digits+"d", i);
        System.out.println();
        for (int j = 0; j < input.length; j++)
        {
            System.out.printf(" %"+digits+"d", input[j]);
            for (int i = 1; i <= n; i++)
                System.out.printf(" %"+digits+"d", m[i][j]);
            System.out.println();
        }

        // Answer:
        long answer = 0;
        for (int i = 0; i < input.length; i++)
            answer += m[n][i];
        System.out.println("\nThe number of possibilities to form "+n+
            " using the numbers "+Arrays.toString(input)+" is "+answer);
    }
}