java - 如何查找数组中的任何值加起来是否为 n

Question

我有一组随机值和一个目标值。

#!/bin/bash
objective='50'
declare -a values=(1 2 2 6 8 14.5 15 28.7 .. 42)

我需要找到一种方法来提取数组“值”中加起来为 50 的任意数字组合

数组有重复项和浮点整数。

解决方案集可能如下所示:

50 = 42 + 8
50 = 42 + 6 + 2

最初我在 bash 中使用了一些嵌套的 for 循环，但是我很快意识到这将随着我的数组长度呈指数增长。

我在大学里上了几门 Java 类(class)，但我在编程方面仍然缺乏经验。我开始认为这可能需要递归。

有更多编程经验的人能为我指明正确的方向吗？
除了嵌套 for 循环之外，您还能如何解决这个问题？

Answer 1

这是一个时间复杂度为 O(M*N) 的算法，其中 M 是目标，N 是集合的总大小。使用背包问题类比如下:-

1. Knapsack capacity = Target
2. Items are elements in the set with weight & value same as itself
3. Calculate maximum profit using dynamic programming
4. maxprofit = Target then there is/are subset which sum up to target.
5. Retrace the solution.

相同的 Java 解决方案:-

public class SubSetSum {
    static int[][] costs;

    public static void calSets(int target,int[] arr) {

        costs = new int[arr.length][target+1];
        for(int j=0;j<=target;j++) {
            if(arr[0]<=j) {

                costs[0][j] = arr[0]; 
            }
        }
        for(int i=1;i<arr.length;i++) {

            for(int j=0;j<=target;j++) {
                costs[i][j] = costs[i-1][j];
                if(arr[i]<=j) {
                    costs[i][j] = Math.max(costs[i][j],costs[i-1][j-arr[i]]+arr[i]);
                }
            }

        }

        System.out.println(costs[arr.length-1][target]);
       if(costs[arr.length-1][target]==target) {
           System.out.println("Sets :");
           printSets(arr,arr.length-1,target,"");
       } 

       else System.out.println("No such Set found");

    } 

    public static void printSets(int[] arr,int n,int w,String result) {


        if(w==0) {
            System.out.println(result);
            return;
        }

        if(n==0) {
           System.out.println(result+","+arr[0]);
            return; 
        }

        if(costs[n-1][w]==costs[n][w]) {
            printSets(arr,n-1,w,new String(result));
        }
        if(arr[n]<=w&&(costs[n-1][w-arr[n]]+arr[n])==costs[n][w]) {
            printSets(arr,n-1,w-arr[n],result+","+arr[n]);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,8,9,7};
        calSets(10,arr);
    }
}