Packing problem [problem description] There is a box capacity of V (positive integer, 0 ≤ V ≤ 20000), and N items (0 ≤ N ≤ 30), each item has a volume (positive integer). In the N items, the remaining space of the box is minimized from the N items.
[Sample]
Enter: 24 an integer, indicating that the box capacity is 6 integers, indicating that N items 8 next N rows, indicating the respective volume of the N items. 3 12 7 9 7
Output: 0 an integer, indicating the remaining space of the box
Algorithm analysis: This question is a classic problem: 0-1 special examples of backpacks (enhance known conditions). Store the volume of each piece of item by plastic array VOLUME, using Boolean Functions h (i, k) to indicate whether the first I item can just fill the capacity K by a combination, consider the Item I, if not selected, The problem is conversion to h (i-1, k); if the first item is selected, the problem is converted to h (I-1, K-Volume [I]), so there is an expression: h (i , K) = h (I-1, K-Volume [I]) || h (i-1, k);
K starts down from V, determining if h (n, k) is true, the first symbol requires the volume consumed by the remaining space. If you write a program directly, you have to define a two-dimensional array, the spatial complexity is n * v, note that N, V is large, so there is a problem with two-dimensional array storage.
It is noted that the value of H (i, k) is only related to H (i-1, K), and if h (i-1, k) = true, there is inevitable H (i, k) = true, H (i, k) has inheritance, while the program ends, we only care about H (n, k), so we can store with one-dimensional array h (k) Intermediate information. In order to avoid repeating calculations, K can change from large to small, in order to avoid negative numbers, K's variation range is V ~ Volume [I].
Sample program:
