import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;

import static java.lang.Math.*;

public class Knapsack_Problem
{
    private static BigDecimal zero = new BigDecimal("0");
    private static BigDecimal half = new BigDecimal("0.5");

    public static void main(String[] args) {
        int[] a = {12, 11, 10, 9, 33, 44, 55, 66};
        int S = 100;
        ArrayList<BigDecimal[]> C = new ArrayList<>();
        ArrayList<BigDecimal[]> b = new ArrayList<>();
        BigDecimal[] c = new BigDecimal[a.length + 1];
        BigDecimal[] x = new BigDecimal[a.length];
        Arrays.fill(c, zero);

        //step 1
        double m = ceil(sqrt(a.length) * 0.5);

        //step 2
        for (int i = 0; i < a.length; i++) {
            c[i] = new BigDecimal(1);
            c[a.length] = new BigDecimal(m * a[i]);
            C.add(c.clone());
            Arrays.fill(c, zero);
        }
        Arrays.fill(c, half);
        c[a.length] = new BigDecimal(S * m);
        C.add(c.clone());
        for (BigDecimal[] aB : C) {
            for (BigDecimal anAB : aB) System.out.print(anAB + " ");
            System.out.println();
        }

        LLL lll = new LLL(C);
        b = lll.getResult();

        //step 3
        Boolean flag = true;

        for (int i = 0; i < b.size(); i++) {
            for (int j = 0; j < b.get(i).length - 2; j++)
                if (!b.get(i)[j].equals(0.5) && !b.get(i)[j].equals(-0.5))
                    flag = false;
            if (b.get(i)[b.get(i).length - 1].equals(0) && flag) {
                for (int j = 0; j < b.get(i).length - 2; j++) {
                    x[j] = b.get(i)[j];
                    x[j].add(half);
                }
                BigDecimal sum = BigDecimal.ZERO;
                for (int j = 0; j < b.get(i).length - 2; j++)
                    sum.add(x[j].multiply(new BigDecimal(a[j])));
                if (sum.equals(S))
                    for (int k = 0; k < x.length; k++) {
                        System.out.println(x[k] + " ");
                        break;
                    }

                for (int j = 0; j < b.get(i).length - 2; j++) {
                    x[j] = b.get(i)[j].negate();
                    x[j].add(half);
                }
                BigDecimal sum1 = BigDecimal.ZERO;
                for (int j = 0; j < b.get(i).length - 2; j++)
                    sum1.add(x[j].multiply(new BigDecimal(a[j])));
                if (sum1.equals(S))
                    for (int k = 0; k < x.length; k++) {
                        System.out.println(x[k] + " ");
                        break;
                    }
            }
        }

        System.out.println("Решений нет");
    }
}