配列のベクトルから数kの要素を合計した配列を作る

Question

私は整数のn個の配列（配列と呼ぶ）と番号kを持つベクトルを持っています。私はベクトルを作る方法を見つけなければなりません。すべての要素の和がk、Sol [i]がArrays [i]であるという性質を持つ、それをSolと呼ぶことにしましょう。 例：

最初はn、2番目はk、次に配列です。

入力：

3 10 
1 2 3 
2 5 7 
4 6 8 

コンソール：私は単にバックトラック使用することができますが、巨大な複雑さがある

2 2 6 

。

3 10 
1 2 3 
2 5 7 
4 6 8 

ex for: 
8 < 10, viable solution 
6 < 10, viable solution 
4 < 10, viable solution 

7 + 8 = 15 < 10 false never check this path again 
7 + 6 = 13 < 10 false never check this path again 
... 

が、私はこれを行う場合であっても、大きな複雑さのためにいくつかの状況があります：私は下から開始し、各ポイントのためにそれは次のように可能な解決策のリストを作り、下からのポイントを組み合わせたアルゴリズムを作ってみました。私はO（m * k）の複雑さを目指しています。ここで、mはすべての入力配列の長さの合計です。

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Iterator; 
import java.util.Scanner; 
import java.util.Vector; 

public class Main { 
    static Vector<Vector<Integer>> Arrays; 
    static int Arrays_lenght; 
    static int sum; 

    public static void main(String[] args) throws FileNotFoundException 
    { 
     Scanner data_in = new Scanner(new File("data.in")); 
     Arrays_lenght = data_in.nextInt(); 
     sum = data_in.nextInt(); 

     Arrays = new Vector<>(); 
     data_in.nextLine(); 

     //read vectors 
     for(int i = 0; i < numar_vectori; i++) 
     { 
      String temp = data_in.nextLine(); 
      Scanner _temp = new Scanner(temp); 
      Vector<Integer> temp_vector = new Vector<>(); 
      while (_temp.hasNext()) { 
       temp_vector.add(_temp.nextInt()); 
      } 
      Arrays.add(temp_vector); 
     } 

     Iterator<Vector<Integer>> itr = Arrays.iterator(); 
     while (itr.hasNext()) 
      System.out.printf("%s\n", itr.next().toString()); 
    } 
} 

ここで私のコードはjavaの入力ファイルを読み込んでいます。どのようにしてSolベクトルをO（m * k）の複雑さで作ることができますか？mはすべての入力配列の長さの合計です。

Answer 1

動的プログラミング溶液（Iは入力配列A[][]は自然数を含んでいると仮定）：

2DアレイB[][]作成 - N行、K + 1列をゼロで埋めます。

for every element of the first input array el=A[0][ix] 
    set B[0][el] = ix+1 
    // incrementing is useful to separate filled entries from empty ones 

for i = 1 to n-1 
    for every element of i-th input array `el=A[i][ix]`: 
     for every ik index in range 0..Sum-el 
      if B[i - 1, ik] is filled then 
       set B[i, ik + el] = ix+1 

at the end: 
if B[N-1, K] is filled 
    unwind indexes of elements that produce needed sum 

第二段階は、（第一のアレイの行を除く）入力行列のすべての要素に対してK回件まで行うので、時間計算量はO（K×m個）です。