java - 给定数组表示 S 所需的最小数字计数

Question

给定一个整数 S 和一个数组 arr[]，任务是找到和为 S 的元素的最小数量，使得数组的一个元素只能被选择一次以获得和 S。

例子：

Input: arr[] = {25, 10, 5}, S = 30 
Output: 2 

解释：

Minimum possible solution is 2, (25+5)

例子：

Input: arr[] = {2, 1, 4, 3, 5, 6}, Sum= 6 
Output: 1 

解释：

Minimum possible solution is 1, (6)

我在这里找到了类似的解决方案，但它说数组元素可以多次使用。

我有来自链接的这段代码，它多次使用数组元素，但是如何限制它只使用一次？

static int Count(int S[], int m, int n)
{
    int [][]table = new int[m + 1][n + 1];
 
    // Loop to initialize the array
    // as infinite in the row 0
    for(int i = 1; i <= n; i++)
    {
    table[0][i] = Integer.MAX_VALUE - 1;
    }
 
    // Loop to find the solution
    // by pre-computation for the
    // sequence
    for(int i = 1; i <= m; i++)
    {
    for(int j = 1; j <= n; j++)
    {
        if (S[i - 1] > j)
        {
            table[i][j] = table[i - 1][j];
        }
        else
        {
                 
            // Minimum possible for the
            // previous minimum value
            // of the sequence
            table[i][j] = Math.min(table[i - 1][j],
                            table[i][j - S[i - 1]] + 1);
        }
    }
    }
    return table[m][n];
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 9, 6, 5, 1 };
    int m = arr.length;
     
    System.out.print(Count(arr, m, 11));
}

标签： javaarraysalgorithm

Answer 1

惯用的方法是在更新先前结果表时向后循环。

static int minElementsForSum(int[] elems, int sum){
    int[] minElems = new int[sum + 1];
    for(int i = 1; i <= sum; i++) minElems[i] = Integer.MAX_VALUE;
    for(int elem: elems) 
        for(int i = sum; i >= elem; i--) 
            if(minElems[i - elem] != Integer.MAX_VALUE) 
              minElems[i] = Math.min(minElems[i], minElems[i - elem] + 1);
    return minElems[sum];
}

Demo