| package ru.maxkar.java;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class Generator {
private static final int PAR = 8;
private static final int PAR_MIN = 300;
private static final ExecutorService exec = Executors
.newFixedThreadPool(PAR);
private static void doRange(int[] cur, int[] next, int id, int size,
int min, int max) {
for (int i = min; i < max; i++)
if (cur[i] >= 0)
next[i + size] = id;
}
public static void fillProducts(int[] cur, int[] next, int id, int size) {
doRange(cur, next, id, size, 0, cur.length - size);
}
public static void fillProductsPar(final int[] cur, final int[] next,
final int id, final int size) {
final int realLast = (cur.length - size);
final int step = realLast / PAR;
int ptr = 0;
final List<Future<?>> futures = new ArrayList<>();
for (int i = 0; i < PAR - 1; i++) {
final int start = ptr;
final int end = ptr + step;
futures.add(exec.submit(new Runnable() {
@Override
public void run() {
doRange(cur, next, id, size, start, end);
}
}));
ptr = end;
}
final int lastPtr = ptr;
futures.add(exec.submit(new Runnable() {
@Override
public void run() {
doRange(cur, next, id, size, lastPtr, realLast);
}
}));
for (Future<?> f : futures)
try {
f.get();
} catch (InterruptedException e) {
// FIXME: !
} catch (ExecutionException e) {
// FIXME: !
}
}
public static void fillProductsAny(int[] cur, int[] next, int id, int size) {
final int realLast = (cur.length - size);
if (realLast <= PAR_MIN)
fillProducts(cur, next, id, size);
else
fillProductsPar(cur, next, id, size);
}
public static void printAnswer(int[][] ans, int sum, int[] weights) {
if (ans[ans.length - 1][sum] == -1) {
System.out.println("Not found");
return;
}
System.out.print("Found :");
int rest = sum;
int ptr = ans[ans.length - 1][rest];
while (ptr > 0) {
final int wname = ptr - 1;
System.out.print(" " + weights[wname]);
rest -= weights[wname];
ptr = ans[wname][rest];
}
System.out.println();
}
public static void printAnswerAlt(int[][] ans, int sum, int[] weights) {
if (ans[ans.length - 1][sum] == -1) {
System.out.println("Not found");
return;
}
System.out.print("Found :");
int rest = sum;
for (int i = weights.length; i -- > 0;) {
if (ans[i][rest] < 0) {
final int w = weights[i];
System.out.print(" " + w);
rest -= w;
}
}
System.out.println();
}
public static void qsolve(int sum, int[] weights) {
final int[][] steps = new int[weights.length + 1][];
final int[] start = new int[sum + 1];
Arrays.fill(start, -1);
start[0] = 0;
steps[0] = start;
int[] queue = new int[sum + 1];
int queec = 1;
queue[0] = 0;
for (int i = 0; i < weights.length; i++) {
final int[] next = steps[i].clone();
final int id = i + 1;
steps[id] = next;
final int w = weights[i];
final int queel = queec;
for (int queep = 0; queep < queel; queep++) {
final int qw = queue[queep];
final int nw = qw + w;
if (nw <= sum && next[nw] < 0) {
next[nw] = id;
queue[queec++] = nw;
}
}
}
printAnswer(steps, sum, weights);
}
public static void solve(int sum, int[] weights) {
final int[][] steps = new int[weights.length + 1][];
int[] current = new int[sum + 1];
Arrays.fill(current, -1);
current[0] = 0;
steps[0] = current;
for (int i = 0; i < weights.length; i++) {
final int id = i + 1;
final int[] next = current.clone();
steps[id] = next;
fillProductsAny(current, next, id, weights[i]);
current = next;
}
printAnswer(steps, sum, weights);
printAnswerAlt(steps, sum, weights);
}
/**
* @param args
*/
public static void main(String[] args) {
solve(1, new int[] { 1, 2, 4, 6, 8, 16, 32, 64, 128, 256 });
solve(100, new int[] { 1, 2, 4, 6, 8, 16, 32, 64, 128, 256 });
solve(321230, new int[] { 16648, 28450, 13524, 12991, 13593, 4797,
18596, 10680, 17865, 25254, 23808, 27379, 6657, 3325, 7573,
5126, 14361, 17311, 4578, 9632, 12375, 15291, 13814, 7935,
22872, 26001, 7895, 9854, 20650, 3317, 23612, 5258, 15092,
1171, 7528, 26422, 19202, 23453, 18628, 4293, 15008, 24880,
24119, 21476, 29331, 3093, 8820, 11034, 6879, 29859, 24913,
22327, 29880, 24401, 383, 28490, 1960, 7673, 29307, 19311,
24713, 2632, 11248, 2261, 17632, 16322, 26870, 17694, 23047,
13155, 15627, 11247, 25238, 8480, 6236, 4343, 16317, 2668,
11793, 9485, 10799, 4823, 16498, 23618, 14526, 12048, 18346,
28581, 7984, 731, 17158, 26949, 21531, 23965, 17754, 12625,
7170, 1924, 26609, 21243, 18748, 13556, 19710, 25036, 8157,
23372, 26228, 353, 24819, 11351, 28590, 10866, 14783, 895,
15260, 15715, 2238, 26571, 14970, 13764, 19156, 6041, 1615,
2947, 24500, 19495, 9775, 4290, 9661, 1083 });
exec.shutdown();
}
}
|