這裏的最少數量是一個例子: 假設我有一個2D陣列僅包括0和1:找到柱
0,1,0,0
0,0,0,1
1,0,1,0
我需要找到最少數量的列的其中最多可以被添加到那些向量。例如, column0 + COLUMN1 +欄3 = 0,0,1 + 1,0,0 + 0,1,0 = 1,1,1
所以,柱的最小數爲3
這裏的最少數量是一個例子: 假設我有一個2D陣列僅包括0和1:找到柱
0,1,0,0
0,0,0,1
1,0,1,0
我需要找到最少數量的列的其中最多可以被添加到那些向量。例如, column0 + COLUMN1 +欄3 = 0,0,1 + 1,0,0 + 0,1,0 = 1,1,1
所以,柱的最小數爲3
這基本上是一個Set cover problem,這是NP難題。它可以作爲整數線性規劃問題來制定和解決(最佳)。
您也可以將問題轉化爲另一個具有很好求解器的同類問題,例如,布爾SAT。最後但並非最不重要的是,您可以使用貪婪和/或本地搜索算法(例如,模擬退火。
無恥複製組合代碼:https://stackoverflow.com/a/34588366/1203882
import java.util.ArrayList;
import java.util.List;
public class Combin {
public static void main(String... banana) {
int[][] input = new int[][] { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 1, 0 } };
List<int[]> columns = new ArrayList<int[]>();
int min = Integer.MAX_VALUE;
//Set columns list
for (int column = 0; column < input[0].length; column++) {
int[] e = new int[input.length];
int index = 0;
for (int row = 0; row < input.length; row++) {
e[index++] = input[row][column];
}
columns.add(e);
}
//Sizes 0 1 2 3 and 4
for (int i = 0; i <= columns.size(); i++)
{
List<List<int []>> theList = getCombinations(i, columns);
for (List <int[]> a : theList)
{
if (check(a))
{
if (a.size() < min)
min = a.size();
//For the test returns 3, 3, and 4 as possibilities.
System.out.println("Found a possibility: " + a.size());
}
}
}
System.out.println("Min value: " + min);
}
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
//Create a vector by "or"ing every value.
public static boolean check(List<int []> result)
{
if (result.size() == 0)
return false;
int [] a = new int [result.get(0).length];
for(int [] j : result)
for (int index = 0; index < a.length; index++)
a[index] |= j[index];
return equalsVec(a);
}
//If all values aren't 1, return false. (ones vector)
public static boolean equalsVec(int [] a)
{
for (int i = 0; i < a.length; i++)
if (a[i] != 1)
return false;
return true;
}
}
輸出:
Found a possibility: 3
Found a possibility: 3
Found a possibility: 4
Min value: 3