Basic algorithm (1) (PASCAL) ZZ

P [I, J]: = P [k, j];

END;

END;

C. Dijkstra algorithm:

Similar reference numerals, essence is a greedy algorithm.

VAR

A: array [1..maxn, 1..maxn] of integer;

B, pre: array [1..maxn] of integer; {pre [i] refers to the front disseval point of i on the shortest path.

Mark: array [1..maxn] of boolean;

Procedure Dijkstra (V0: Integer);

Begin

Fillchar (Mark, SizeOf (Mark), False;

For i: = 1 to n Do Begin

D [i]: = a [v0, i];

IF D [i] <> 0 THEN PRE [I]: = V0 else pre [I]: = 0;

END;

Mark [v0]: = true;

Repeat {Add a nearest node close to 1 episodes per loop and adjust the parameters of other nodes}

MIN: = Maxint; u: = 0; {u Record from 1 episode nearest node}

For i: = 1 to n DO

IF (Not Mark [i]) and (d [i]

u: = i; min: = d [i];

END;

IF u <> 0 THEN Begin

Mark [u]: = true;

For i: = 1 to n DO

IF (Not Mark [i]) and (a [u, i] d [u]

D [i]: = a [u, i] d [u];

Pre [i]: = u;

END;

END;

Until u = 0;

END;

D. Transfer closure of the calculation map

PROCEDURE longlink;

VAR

T: array [1..maxn, 1..maxn] of boolean;

Begin

Fillchar (T, SizeOf (t), false;

Fork: = 1 to n DO

For i: = 1 to n DO

For j: = 1 to n DO T [i, j]: = T [i, j] or (t [i, k] and t [k, j]);

END;

6.0-1 backpack problem (some backpack issues can have a greed method: 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 has a volume (positive integer). Requires from N items, if you have a thousand loading boxes, the remaining space of the box is minimized.

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] =

C. Ask the number of applications that is full.

(2) Each backpack can use any time:

A. Ask for maximum weight.

The state transfer equation is

F [i, j] = max {f [i-w [j]

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, each of the topics can be selected, each topic has a Ti (answer the time required to answer this question) and a Si (answer this question) The resulting score), now choose a number of questions, the total number of points obtained by the total time of these questions, the maximum score obtained, and the maximum score.

* It is easy to think:

F [i, j] = max {f [i-k * w [j], j-1] k * v [j]} (0 <= k <= I DIV W [J])

Where F [I, J] indicates that the maximum value that the front J table backpack can achieve when the capacity is i.

*optimization:

Begin

Fillchar (Problem, SizeOf (Problem), 0);

Assign (Input, 'Inflate.in');

RESET (INPUT);

Readln (M, N);

For i: = 1 to n DO

WITH Problem [i] DO

Readln (Point, TIME);

Close (INPUT);

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;

Assign (Output, 'Inflate.out');

Rewrite (OUTPUT);

Writeln (f [m]);

Close (Output);

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 2, recursive search efficiency is higher 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;

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]);