我有一个包含 n 个整数数组(我们称之为数组)和一个数字 k 的 vector 。我必须找到一种方法来制作一个 vector ,我们称它为 Sol,其所有元素的总和为 k,而 Sol[i] 来自 Arrays[i]。 例如:
首先是 n,其次是 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 读取输入文件的代码。我如何制作复杂度为 O(m*k) 的 Sol vector ,其中 m 是所有输入数组的长度之和?
最佳答案
动态规划方案(假设输入数组A[][]
包含自然数):
创建二维数组 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)。
关于java - 从数组 vector 中创建一个元素总和等于数字 k 的数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41470788/