Dynamic Programming Classic Tutorial
Introduction: After solving some problems, I have some thoughts on DP, so I wrote this summary:
Section 1 Basic Concepts of Dynamic Programming
- The three elements of dynamic programming: stages, states, decisions.
Their concepts are everywhere, so I won't elaborate much; I'll just share my understanding of them:
If we consider the process of solving dynamic programming as a factory production line, the stage represents different links in producing a certain product, the state represents the current form of the workpiece, and the decision represents the operation on the workpiece. Clearly, different stages summarize the various states of the product, and these small summaries form the entire production line. There are also relationships between each state (the next state is generated after a certain decision is made from the previous state).
Let me give an example:
To produce a batch of ice cream, there are many steps in this process: buying milk, purifying the milk, processing it in the factory, packaging the processed product, and then selling it... Each step can be seen as a stage; the product has different states at different times. At the beginning, it is just plain milk, then it is shaped during production, and after being taken out of the freezer, it becomes ice cream (changing from liquid to solid =_=||). Each form is a state, and the operation of freezing is a decision that changes the state from liquid to solid.
A state changes to another state through a decision; this process is called state transition, and the equation used to describe state transitions is the state transition equation.
After this example, I believe everyone has some understanding of dynamic programming.
Next, I will discuss another understanding of dynamic programming:
Understanding dynamic programming through graph theory: Abstract the states in dynamic programming into points, and connect directly related states with directed edges. The cost of state transition is the weight on the edge. This forms a directed acyclic graph (DAG) (why acyclic? Read on). Perform a topological sort on this graph, and after deleting an edge, the states with an in-degree of 0 appear in the same stage. Thus, finding the optimal path in the graph is the solution to the dynamic programming problem. - Applicable Scope of Dynamic Programming
Dynamic programming is used to solve multi-stage decision optimization problems, but not all optimization problems can be solved with dynamic programming, right?
Generally, when a problem appears that seeks an optimal solution, dynamic programming should be considered, but it must also satisfy two conditions:
Optimal substructure (principle of optimization)
No aftereffect
The principle of optimization is detailed in the shortest path problem below;
What is no aftereffect?
It means that when solving state i, if state j is used, and state j uses state k... state N.
And when solving state N, state i is used, then the process of solving the state forms a cycle, making it impossible to solve with dynamic programming. This is also the reason why the graph formed in the understanding of dynamic programming through graph theory is acyclic.
In other words, the current state is a perfect summary of the previous states, and the present is unrelated to the past...
Of course, if you change the way of dividing states or stages, it can still satisfy no aftereffect, and such problems can still be solved with dynamic programming. - General Idea for Solving Problems with Dynamic Programming.
After obtaining a multi-stage decision optimization problem, the first step is to determine whether this problem can be solved with dynamic programming. If not, consider search or greedy methods. Once it is determined that the problem can be solved with dynamic programming, the following methods should be used to solve the problem:
(1) Model Matching Method:
The first method to consider is this one. Dig into the essence of the problem; if you find that the problem is a familiar basic model, apply it directly, but be careful of some small changes. Nowadays, exam questions often apply basic models in a transformed way, so think twice before acting. These basic models will be introduced one by one in the previous classification.
(2) Three Elements Method
Carefully analyze the problem and try to determine the three elements of dynamic programming. Different problems have different determination directions:
First determine the stage: the number tower problem and the walking problem (see the problem-solving report for details)
First determine the state: most problems first determine the state.
First determine the decision: the knapsack problem. (See the problem-solving report for details)
Generally, start from the more obvious places. As for how to know which is obvious, that’s an experience issue; doing more problems will help you discover it.
(3) Finding Patterns Method:
This method is very simple; patiently push a few sets of data, observe their patterns, and summarize the commonalities between the patterns, which has a bit of a greedy feel to it.
(4) Boundary Conditions Method
Find the boundary conditions of the problem, and then consider the relationship between the boundary conditions and their adjacent states. This method is also very effective.
(5) Relaxing Constraints and Adding Constraints
This idea was seen in Chen Qifeng's paper, specifically adding some conditions or removing some conditions to clarify the problem.
Section 2 Classification Discussion of Dynamic Programming
Here, dynamic programming is classified based on the dimensions of the state: - The state is one-dimensional
1.1 Decreasing/Non-decreasing Subsequence Problem:
Problem Description: {Dig into the essence of the problem; once abstracted into this description, you can solve it with this method}
In an unordered sequence a1, a2, a3, a4... an, find the longest sequence that satisfies: ai <= aj <= ak... <= am, and i < j < k... aj > ak... > am, and i > j > k... > m. (Longest decreasing subsequence).
Problem Analysis:
If in the first i-1 numbers ak is used (ak > ai or akai (or aj <= ai), opt[j] + 1 is the value of opt[i]; represented by the equation: {I am used to this writing style, but it is not the standard writing style of the state transition equation}
opt[i] = max(opt[j]) + 1 (0 <= j < i and aj <= ai) {Longest non-decreasing subsequence}
opt[i] = max(opt[j]) + 1 (0 <= j < i and aj > ai) {Longest decreasing subsequence}
Implementation of the solving part of the code:
opt[0] := maxsize; {maxsize is maxlongint or -maxlongint}
for i := 1 to n do
for j := 0 to i - 1 do
if (a[j] > a[i]) and (opt[j] + 1 > opt[i]) then
opt[i] := opt[j] + 1;
ans := -maxlongint;
for i := 1 to n do
if opt[i] > ans then ans := opt[i]; {ans is the final solution}
Complexity: From the above implementation, it is not difficult to see that the time complexity is O(N^2), and the space complexity is O(N);_
Example 1 Intercepting Missiles (missile.pas/c/cpp) Source: NOIP1999 (Advanced Group) First Question
【Problem Description】
In order to defend against missile attacks from enemy countries, a certain country has developed a missile interception system. However, this missile interception system has a flaw: although its first shell can reach any height, every subsequent shell cannot be higher than the previous shell. One day, radar detected an incoming missile from the enemy country. Since the system is still in the trial phase, there is only one set of the system, so it may not be able to intercept all missiles.
Input the heights of the missiles flying in sequence (the radar gives height data that is a positive integer not exceeding 30000), and calculate how many missiles this system can intercept at most. If all missiles are to be intercepted, how many sets of this missile interception system must be equipped at least.
【Input File】 missile.in
A single line lists the heights of the missiles flying in sequence.
【Output File】 missile.out
Two lines, the first is the maximum number of missiles that can be intercepted, and the second is the minimum number of systems needed to intercept all missiles.
【Input Sample】
389 207 155 300 299 170 158 65
【Output Sample】
6
2
【Problem Analysis】
Experienced competitors will find that this is a problem of finding the longest non-increasing subsequence, and the standard algorithm is dynamic programming.
Taking the order of the missiles flying in sequence as stages, design the state opt[i] to represent the maximum number of missiles that can be intercepted when intercepting missile i among the first i missiles.
State transition equation:
opt[i] = max(opt[j]) + 1 (h[i] >= h[j], 0 <= j < i) and (opt[j] + 1 > opt[i]) then
opt[i] := opt[j] + 1;
anslen := 0;
for i := 1 to n do
if opt[i] > anslen then
anslen := opt[i];
fillchar(opt, sizeof(opt), 0);
a[0] := -maxlongint;
for i := 1 to n do
for j := i - 1 downto 0 do
if (a[j] > a[i]) then
opt[i] := opt[j] + 1;
anstime := 0;
for i := 1 to n do
if opt[i] > anstime then
anstime := opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end._
Example 2 Chorus Formation (chorus.pas/c/cpp) Source: NOIP2004 (Advanced Group) First Question
N students stand in a row, and the music teacher wants to ask (N-K) of them to step out so that the remaining K students can form a chorus formation.
A chorus formation is defined as follows: if the K students are numbered from left to right as 1, 2..., K, and their heights are T1, T2,..., TK, then their heights must satisfy T1 < ... Ti + 1 > ... > TK (1 <= i <= K).
Your task is to calculate the minimum number of students that need to step out so that the remaining students can form a chorus formation, given the heights of all N students.
【Input File】
The first line of the input file is an integer N (2 <= N <= 100), indicating the total number of students. The first line contains N integers separated by spaces, where the i-th integer Ti (130 <= Ti <= 230) is the height of the i-th student (in cm).
【Output File】
The output file chorus.out contains a single line with a single integer, indicating the minimum number of students that need to step out.
【Sample Input】
8
186 186 150 200 160 130 197 220
【Sample Output】
4
【Data Scale】
For 50% of the data, it is guaranteed that N <= 20;
For all data, it is guaranteed that N <= 100.
【Problem Analysis】
The minimum number of students stepping out means that the remaining students are maximized, which means finding the longest subsequence.
This analysis is a typical longest decreasing subsequence problem. Just enumerate each person standing in the middle to find the optimal solution. Clearly, it is equal to finding the longest increasing subsequence to the left and the longest decreasing subsequence to the right, including the person in question.
Let’s look at the complexity:
The complexity of calculating the longest decreasing subsequence is O(N^2), and since we find N times, the total complexity is O(N^3). This complexity is acceptable for the data range of this problem. But is there a better method?
In fact, the longest subsequence can be found in one go. Because the longest decreasing (or increasing) subsequence is not affected by the middle person.
Just use OPT1 to find the longest increasing subsequence once, and OPT2 to find the longest decreasing subsequence once. Thus, the answer is N - max(opt1[i] + opt2[i] - 1).
The complexity is reduced from O(N^3) to O(N^2).
【Source Code】
program chorus;
const
fin='chorus.in';
fout='chorus.out';
maxn=200;
var
opt1,opt2,a0..maxn of longint;
n,ans;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=0 to i-1 do
if (a[j] > a[i]) and (opt1[j] + 1 > opt1[i]) then
opt1[i] := opt1[j] + 1;
a[n+1]:=-maxlongint;
for i:=n downto 1 do
for j:=i+1 to n+1 do
if (a[j] > a[i]) and (opt2[i] < opt2[j] + 1) then
opt2[i] := opt2[j] + 1;
ans:=0;
for i:=1 to n do
if opt1[i] + opt2[i] > ans then
ans := opt1[i] + opt2[i];
end;
procedure print;
begin
writeln(n-ans+1);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
Example 3 Buy Low Buy Lower (buylow.pas/c/cpp) Source: USACO 4-3-1
【Problem Description】
"Buying low" is a successful secret to stock trading. If you want to become a successful investor, you must follow this principle:
"Buy low, the lower the better"
This means that every time you buy stocks, the stock price must be lower than the price at which you last bought. The more times you buy stocks according to this rule, the better. See how many times you can buy under this rule.
Given the stock prices for N consecutive days, you can buy stocks on any day, but the price at which you buy must be lower than the price at which you last bought. Write a program to find out how many times you can buy stocks at most.
For example, the stock prices for several days are:
Days 1 2 3 4 5 6 7 8 9 10 11 12
Prices 68 69 54 64 68 64 70 67 78 62 98 87
In this example, a smart investor (according to the above definition) can buy stocks at most 4 times if the price at which he buys stocks is lower than the last time he bought. One possible buying method is as follows (there may be other methods):
Days 2 5 6 10
Prices 69 68 64 62
【Input File】 buylow.in
The first line: N (1 <= N <= 10000) {the number of stock prices}
The second line: the stock prices for N days.
【Output File】 buylow.out
A single line containing a single integer, the maximum number of times stocks can be bought.
【Input Sample】
10
68 69 54 64 68 64 70 67 78 62
【Output Sample】
4
【Problem Analysis】
The problem is to find the longest decreasing subsequence, and the standard algorithm is dynamic programming.
Taking the order of stock prices as stages, design the state opt[i] to represent the maximum number of stocks that can be bought when buying stock i among the first i stocks.
State transition equation:
opt[i] = max(opt[j]) + 1 (h[i] >= h[j], 0 <= j < i) and (opt[j] + 1 > opt[i]) then
opt[i] := opt[j] + 1;
anslen := 0;
for i := 1 to n do
if opt[i] > anslen then
anslen := opt[i];
fillchar(opt, sizeof(opt), 0);
a[0] := -maxlongint;
for i := 1 to n do
for j := i - 1 downto 0 do
if (a[j] > a[i]) then
opt[i] := opt[j] + 1;
ans := -maxlongint;
for i := 1 to n do
if ans < opt[i] then
ans := opt[i];
writeln(ans);
end;
begin
init;
main;
print;
end.
Example 4 Ships (ships.pas/c/cpp) Source: "Classic of Aose" (Advanced Edition)
【Problem Description】
The country of PALMIA is divided into two banks by a river, with N villages on each bank. Each village on the north bank has a unique friend on the south bank, and their friend villages are all different.
Each pair of friend villages wants a boat to connect them, and they apply to the government for approval. Due to frequent fog on the river, the government has decided to prohibit intersecting boat routes (if they intersect, it is likely to cause collisions).
Your task is to write a program to help government officials decide which boat routes to approve so that the maximum number of non-intersecting routes is achieved.
【Input File】 ships.in
The input file consists of several sets of data. The first line of each set contains two integers X and Y, separated by a space, where X represents the length of the PALMIA river (10 <= X <= 6000) and Y represents the width of the river (10 <= Y <= 100). The second line contains an integer N, indicating the number of villages on both banks. In the next N lines, each line contains two non-negative integers C and D, separated by a space, representing the distance of the friend villages along the riverbank from the westernmost boundary of the PALMIA river (C represents the village on the north bank, D represents the village on the south bank). There are no villages on the same side at the same position. The last set of data is followed by a line containing two zeros, separated by a space.
【Output File】 ships.out
For each set of input data, the output file should indicate the maximum number of boat routes that can be approved under the above conditions on consecutive lines.
【Input Sample】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【Output Sample】
4
【Problem Analysis】
This problem is relatively difficult to think about, and it is not immediately obvious what the essence of the problem is. Here I recommend two methods to think about such problems.
Method 1: Finding Patterns Method (the third method I summarized earlier)
To find patterns, you naturally need to push a few sets of data, and of course, start with the examples;
Carefully observe the above figure: the red routes are legal, so what rules do they satisfy?
C1 C2 C3 C4
The endpoints of the red lines on the north bank: 4 9 15 17
The endpoints of the red lines on the south bank: 2 8 12 17
D1 D2 D3 D4
It is not difficult to see that regardless of the slope of the line, there is such a rule:
C1 < C2 < C3 < C4 and D1 < D2 < D3 < D4
If we sort the input data in ascending order, the problem becomes abstract:
Find the longest sequence in a sequence (D) that satisfies DI < DJ < Dk... and i < j < k
In this case, it is a typical longest non-decreasing subsequence problem...
Method 2: Boundary Conditions Method (the fourth method I summarized earlier)
The boundary method is actually about shrinking the data down; obviously, when N=1, the answer is 1. What about when N=2?
Consider such a set of data:
C1 D1
C2 D2
When C1 D2, they must intersect; conversely, they will not intersect.
When C1 > C2, if D1 < D2, they must intersect; otherwise, they will not intersect.
N=3
C1 D1
C2 D2
C3 D3
...
Actually, there is no need to derive N=3; if you are interested, you can derive it. Just looking at N=2 can lead to:
For any two routes, if they satisfy Ci < Cj and Di < Dj, then the two routes do not intersect. Thus, to ensure that all routes do not intersect in a sequence, it must satisfy C1 < C2 < C3... < Cans and D1 < D2 < D3... < Dans, which means that after sorting C, finding the length of the longest sequence that satisfies this condition is the solution.
After this analysis, it is clear that it is a longest non-decreasing subsequence problem.
Complexity: Sorting can be done with an O(n log n) algorithm, and finding the longest non-decreasing subsequence has a time complexity of O(n^2).
The total complexity is O(n^2).
【Source Code】
program ships;
const
fin='ships.in';
fout='ships.out';
maxn=5010;
type
retype=record
C,D;
end;
var
x,y,n,ans;
a0..maxn of retype;
opt0..maxn of longint;
procedure init;
var
i;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r);
var
i,j,x;
y;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].c < x do
inc(i);
while a[j].c > x do
dec(j);
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
inc(i);
dec(j);
end;
until i > j;
if L < j then quick(L,j);
if i < r then quick(i,r);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
quick(1,n);
for i:=1 to n do
for j:=0 to i-1 do
if (a[j].d < a[i].d) then
opt[i] := max(opt[i],opt[j]+1);
ans:=-maxlongint;
for i:=1 to n do
if ans < opt[i] then
ans := opt[i];
writeln(ans);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(x,y);
while (x+y > 0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.
3.3 其他問題
還有一些題目雖然和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的：
例題 32 砝碼稱重 來源：NOIP1996（提高組）第四題
【問題描述】
設有 1g、2g、3g、5g、10g、20g 的砝碼各若干枚（其總重 <=1000），用他們能稱出的重量的種類數。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，…，20g 砝碼有 a6 個，中間有空格）。
【輸出文件】
Total=N
（N 表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 33 砝碼稱重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 34 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 35 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 36 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 37 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 38 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 39 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 40 砝码称重 來源：NOIP1996（提高組）第四题
【问题描述】
设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重 <=1000），用他们能称出的重量的种类数。
【输入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个，中间有空格）。
【输出文件】
Total=N
（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。
【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL=3
【问题分析】
把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的 0/1 背包问题的简化版了，求解方法完全和上面说的一样，只是要注意这个题目不是求最大载重量，而是统计所有的可称出的重量的个数。
【源代码 1】
program P4;
const
maxn=1010;
w1..6 of longint=(1,2,3,5,10,20);
var
opt0..maxn of boolean;
a1..6 of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.