1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 *
 * @author Marcin Lewandowski
 */
public class pak {

    public static void main(String[] args) throws IOException {
        int n = readInt();
        int m = readInt();
        int[] weights = new int[n];
        long weigthSum = 0;
        for (int i = 0; i < n; i++) {
            weights[i] = readInt();
            weigthSum += weights[i];
        }
        int[] backpacks = new int[m];
        long totalCapacity = 0;
        for (int i = 0; i < m; i++) {
            backpacks[i] = readInt();
            totalCapacity += backpacks[i];
        }
        if (weigthSum > totalCapacity) {
            System.out.println("NIE");
            return;
        }
        Arrays.sort(weights);
        Arrays.sort(backpacks);
        if (weights[n - 1] > backpacks[m - 1]) {
            System.out.println("NIE");
            return;
        }
        int minNumberOfBackpacks = 1;
        int capacity = 0;
        for (; minNumberOfBackpacks <= m; minNumberOfBackpacks++) {
            capacity += backpacks[m - minNumberOfBackpacks];
            if (capacity >= weigthSum) {
                break;
            }
        }

        while (minNumberOfBackpacks <= m) {
            int[] currentWeights = weights.clone();
            int availabeCapacity[] = new int[minNumberOfBackpacks];
            for (int i = 0; i < minNumberOfBackpacks; i++) {
                availabeCapacity[i] = backpacks[m - i - 1];
            }
            for (int i = 0; i < minNumberOfBackpacks; i++) {
                boolean[] bestCombination = getCombinationThatFillsCapacity(currentWeights, availabeCapacity[i],(i+1 < minNumberOfBackpacks ? availabeCapacity[i+1]:-1));
                currentWeights = updateWeights(bestCombination, currentWeights);
            }
            if (currentWeights.length == 0) {
                System.out.println(minNumberOfBackpacks);
                return;
            }else{
                minNumberOfBackpacks++;
            }
        }
        System.out.println("NIE");
    }

    private static int[] updateWeights(boolean[] toRemove, int[] currentWeights) {
        ArrayList<Integer> newWeights = new ArrayList<Integer>();
        for (int i = 0; i < currentWeights.length; i++) {
            if (!toRemove[i]) {
                newWeights.add(currentWeights[i]);
            }
        }
        int [] result = new int[newWeights.size()]; 
        for (int i = 0; i < newWeights.size(); i++) {
            result[i] = newWeights.get(i);                
        }
        return result;
    }

    private static int readInt() throws IOException {
        int result = 0;
        boolean isDigit = false;
        int c = 0;
        while ((c = System.in.read()) != -1) {
            if (c >= '0' && c <= '9') {
                isDigit = true;
                result = result * 10 + c - '0';
            } else if (isDigit) {
                break;
            }
        }
        return result;
    }

    private static boolean[] getCombinationThatFillsCapacity(int[] weights, int capacity, int nextCap) {
        long best = 0;
        long usedCapacity = 0;
        LinkedList<Integer> indexes = new LinkedList<Integer>();
        LinkedList<Integer> bestIndexes = new LinkedList<Integer>();
        int end = weights.length-1;
        if(nextCap!=-1 && weights[weights.length - 1]<=nextCap){
            end=0;
        }
        for (int i = weights.length - 1; i >= end; i--) {
            indexes.clear();
            usedCapacity = weights[i];
            indexes.add(i);
            boolean isSomethingToAdd = true;
            int last = i;
            while (isSomethingToAdd && usedCapacity < capacity) {
                isSomethingToAdd = false;
                long diff = capacity - usedCapacity;
                for (int j = last - 1; j >= 0; j--) {
                    if (weights[j] <= diff) {
                        isSomethingToAdd = true;
                        indexes.add(j);
                        last=j;
                        usedCapacity += weights[j];
                        break;
                    }
                }
            }
            if (usedCapacity > best && usedCapacity <= capacity) {
                best = usedCapacity;
                bestIndexes = new LinkedList<Integer>(indexes);
            }
        }
        boolean[] result = new boolean[weights.length];
        for (int i = 0; i < result.length; i++) {
            if (bestIndexes.contains(i)) {
                result[i] = true;
            }
        }
        return result;
    }
}