Third, backpack problem
* Some backpack problems can have greedy solution: calculate PI / Wi
data structure:
w [i]: the weight of the i-th backpack;
p [i]: The value of the i-th backpack;
1.0-1 Backpack: Each backpack can only use once or limited (convertible to once):
A. Ask for maximum weight.
NOIP2001 packing problem
There is a box capacity of V (positive integer, o ≤ V ≤ 20000), and N items (O ≤ N ≤ 30), each item
There is a volume (positive integer). Require from N items, if you take a thousand loading, make the remaining space of the box
It is the smallest.
l search method
Procedure Search (K, V: Integer); {Searching the kth item, the remaining space is V}
Var i, J: integer;
Begin
IF V IF V- (s [n] -s [k-1])> = BEST THEN EXIT; {s [n] is the weight and} of the previous N items. IF K <= n Then Begin IF v> w [k] THEN Search (k 1, v-w [k]); Search (k 1, v); END; END; l dp F [i, j] Select several pieces of the previous I to put it in a marker that is just J J. is a Boolean. Implementation: Transformation of optimized problems into judgment issues F [i, j] = f [i-1, j-w [i]] (w [i] <= j <= v) boundary: f [0 ,0]: = true. For i: = 1 to n DO For j: = w [i] to v DO F [i, j]: = f [i-1, j-w [i]]; Optimization: The current state is only related to the previous stage state, which can be reduced to one dimension. F [0]: = True; For i: = 1 to n Do Begin F1: = f; For J: = W [i] to v DO IF F [J-W [I]] THEN F1 [J]: = true; F: = f1; END; B. The maximum value that can be placed. F [i, j] is the maximum value that the previous J backpack can obtain for the capacity of i. F [i, j] = max {f [i - w [j], j-1] p [j], f [i, j-1]} C. Ask the number of applications that is full. DP: Procedure Update; Var J, K: Integer; Begin C: = a; For j: = 0 to n DO IF a [J]> 0 THEN IF J NOW <= N THEN INC (C [J Now], A [J]); A: = C; END; 2. Repeatable backpack A seeking up to the weight can be placed. F [i, j] Select several pieces of the previous I to put it in a marker that is just J J. is a Boolean. The state transfer equation is F [i, j] = f [i-1, j - w [i] * k] (k = 1 .. J DIV W [i]) B. The maximum value that can be placed. USACO 1.2 Score Inflation Take a competition, the total time T is fixed, there are several optional questions, and each topic can be selected. Each topic has a TI (answer the time required for this question) and a Si (answer the score obtained by this question), now choose Several questions, the total time of these questions is the largest, and the maximum score is maximized. * It is easy to think: F [i, j] = max {f [i-k * w [j], j-1] k * p [j]} (0 <= k <= I DIV W [j]) where F [i , J] indicates the maximum value that the previous J collar bag can achieve when the capacity is i. *achieve: Begin Fillchar (f, sizeof (f), 0); For i: = 1 to m DO For j: = 1 to n DO I-problem [J] .time> = 0 THEN Begin T: = problem [j] .point f [i-quobem [j] .time]; IF T> f [i] THEN F [I]: = T; END; Writeln (f [m]); End. C. Ask the number of applications that is full. Ahoi2001 Problem2 Seeking natural number n Number of nature and the number of expressions. Idea, generate the arrangement of the coefficients of each rigidity, test in one by one, this is a form of a law. Procedure TRY (dep: integer); Var i, J: integer; Begin Cal; {This process calculates the calculation result of the current coefficient, the result is the result} IF now> n kiln exit; {scorch} IF dep = L 1 Then Begin {Generates All Coefficient} Cal; IF now = n THEN INC (TOT); EXIT; END; For i: = 0 to n Div PR [dep] do begin XS [dep]: = i; TRY (DEP 1); XS [dep]: = 0; END; END; Idea II, recursive search efficiency is high Procedure TRY (dep, rest: integer); Var i, j, x: integer; Begin IF (REST <= 0) OR (DEP = L 1) THEN BEGIN IF rest = 0 THEN INC (TOT); EXIT; END; For i: = 0 TO REST DIV PR [DEP] DO TRY (DEP 1, REST-PR [DEP] * i); END; {main: try (1, n);} Ideas 3: Can be solved using dynamic planning USACo1.2 Money System V Item, the backpack capacity is n, and the total number of flasks is found. Transfer equation: Procedure Update; Var J, K: Integer; Begin C: = a; For j: = 0 to n DO IF a [J]> 0 THEN Fork: = 1 to n Div Now DO IF J Now * K <= n THEN INC (C [J Now * K], A [J]); A: = C; END; {main} Begin Read (now); {Reading the weight of the first item} I: = 0; {a [i] is the total number of} when the backpack capacity is i} While i <= n do begin A [I]: = 1; INC (I, NOW); end; {Define the weight a value of the integer number of the first item is 1, as the initial value} For i: = 2 to v DO Begin Read (now); Update; {Dynamic Update} END; Writeln (a [n]);
