如何查找數組中是否有任何值合計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 

起初我在與一些嵌套的for循環bash的開始，但我很快意識到，這將成倍我的數組長度增長。

我在大學裏學了幾個java類，但我在編程方面還沒有經驗。我開始認爲這可能需要遞歸。

任何具有更多編程經驗的人都能指引我走向正確的方向嗎？
除了嵌套for循環，你還能如何解決這個問題？

Answer 1

我會做這樣的：

1.some初始化

const int N=array size; 
int val[N]; // input data 
bool flag[N]; // is val used ? 
for (int i=0;i<N;i++) flag[i]=false; 
sort val[] descending 

2.創建函數布爾find_sum（int類型）;

• ，如果它發現解決方案返回true，否則返回false

• 設置標誌，以適用於所有使用的值

  { 
  for (int i=0;i<N;i++)     // find first usable big number (could be faster with binary search or with tailing last used i index into recursion) 
  if ((val[i]<=s)&&(!flag[i])) 
      { 
      flag[i]=true;       // flag it as used 
      if (val[i]==s) return true;   // try to find reminder 
      if (find_sum(s-val[i])) return true; // if found return true 
      flag[i]=false;       // else unflag val[i] and continue winth next number 
      } 
  return false;       // if sum not found then return false 
  } 
  

3.after find_sum（S）的總和由所有的val [ i]其中flag [i]！= false

[edit1]即使對您的情況功能源測試[6,5,5]和總和= 10它是好的

//--------------------------------------------------------------------------- 
int find_sum(int *val,int *use,int N,int sum,bool init=true) 
    { 
    int i; 
    if (init) 
     { 
     for (i=0;i<N;i++) use[i]=0;   // nothibg used yet 
     for (int e=1;e;)     // bubble sort 
     for (e=0,i=1;i<N;i++) 
      if (val[i-1]<val[i]) 
      { e=val[i-1]; val[i-1]=val[i]; val[i]=e; e=1; } 
     } 
    for (i=0;i<N;i++)      // find first usable big number (could be faster with binary search or with tailing last used i index into recursion) 
    if ((val[i]<=sum)&&(!use[i])) 
     { 
     use[i]=1;       // val[i] is used 
     if (val[i]==sum) return 1;    // try to find reminder 
     if (find_sum(val,use,N,sum-val[i],false)) return 1; // if found return true 
     use[i]=0;       // else val[i] is unused and continue winth next number 
     } 
    return 0;        // if sum not found then return false 
    } 
//--------------------------------------------------------------------------- 
void main() 
    { 
    int in[]={6,5,5}; // input data 
    const int N=sizeof(in)/sizeof(int); 
    int ret,out[N]; 
    if (find_sum(in,out,N,10)) 
    for (int i=0;i<N;i++) 
     if (out[i]) 
     { 
     cout << in[i] << " "; 
     } 
    } 
//--------------------------------------------------------------------------- 

PS。在輸入數組你的問題也浮點值

• 所以你必須改變INT VAL []，和浮動/雙

• ，並添加一些精度和比較花車

  工作

  if (val[i]==sum) return 1; 
  

• 變化到

  if (fabs(val[i]-sum)<1e-10) return 1; 
  

• ，或者使用任何其他ACCURA CY代替1E-10

Answer 2

您可以使用遞歸是的，你可以打破陣列成子部分（我用的List）。

1. 從父親列表的第0指數和空白列表
2. 迭代開始了從i+1 SUBLIST你的父母到底，從而增加從0 to i
3. 檢查的sum您的工作表（計算）等於你的目標

代碼：

static Integer[] array = { 1, 2, 2, 6, 8, 14, 15, 28, 30, 32, 12, 48, 6, 42 }; 
static int objective = 50; 

public static void main(String args[]) { 
    add(new ArrayList<Integer>(Arrays.asList(array)), 
      new ArrayList<Integer>()); 
} 

public static void add(List<Integer> digits, List<Integer> workingList) { 

    for (int i = 0; i < digits.size(); i++) { 
     // New sublist to store values from 0 to i 
     List<Integer> list = new ArrayList<Integer>(workingList); 
     list.add(digits.get(i)); 

     // Here you call this recursively with your Parent list from i+1 
     // index and working list from 0 to i 
     add(digits.subList(i + 1, digits.size()), list); 
    } 

    int sum = 0; 
    for (int element : workingList) { 
     sum += element; 
    } 

    if (sum == objective) { 
     System.out.println(objective + " = " 
       + Arrays.toString(workingList.toArray())); 
    } 

} 

輸出：

50 = [1, 2, 2, 15, 30] 
50 = [1, 2, 6, 8, 15, 12, 6] 
50 = [1, 2, 6, 14, 15, 12] 
50 = [1, 2, 14, 15, 12, 6] 
50 = [1, 2, 15, 32] 
50 = [1, 2, 6, 8, 15, 12, 6] 
... 

Answer 3

這裏是具有時間複雜度O(M*N)而M是目標與N是一整套總大小的算法。作爲本身

計算利潤最大化利用動態規劃

MAXPROFIT

1. 揹包容量=目標
2. 項目是集合中的元素與體重&值相同 - ：按如下方式使用類比揹包問題=目標，那麼總共有目標的子集。
3. 追溯解決方案。

的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); 
    } 
}