Statement
The author is not a professional programmer. This article is just sharing his own experience. If there are many mistakes, please point them out. If you don’t like it, please don’t complain.
This article uses the Pascal language that a novice like the author understands.
This blog is also written for a friend of mine who doesn’t understand code but is very interested in algorithms, so I don’t include some “advanced” elements.
The writing is a bit hasty, please forgive me 😛
This article introducesgreedy algorithm, focusing onpart of the knapsack problem.
This article refers to the detailed explanation of the backpack problem (including code)_Lin 128’s Blog-CSDN Blog
1. Title Description
1.01 Backpack
There are N items and a backpack with capacity V. The space consumed to put the i-th item is Ci, and the value obtained is Wi. Find which items can be packed into a backpack to maximize the total value.
Features: There is only one of each item, you can choose to put it or not. That is, there are two states: 0 (not put) and 1 (put)
2. Partial Backpack
There are N items and a backpack with capacity V. The space consumed to put the i-th item is Ci, the value obtained is Wi, and the item can be divided. Find which items can be packed into a backpack to maximize the total value.
Features: Items can be divided
3. Complete Backpack
There are N kinds of items and a backpack with a capacity V. There are unlimited pieces of each item available. The cost of putting the i-th item is Ci and the value is Wi. Solution: Which items can be put into the backpack so that the total cost of these items does not exceed the backpack capacity and the total value is the largest.
Features: Each item can be used unlimitedly
4.Multiple backpacks
There are N kinds of items and a backpack with capacity V. There are at most Mi items available for the i-th item, the space consumed by each item is Ci, and the value is Wi. Find out which items can be packed into the backpack so that the total space consumed by these items does not exceed the capacity of the backpack and the total value is the largest.
Features: The quantity of each item is different
5. Other backpacks…
Group backpacks, Associated backpacks…and those backpack problems that don’t look like backpack problems…
Lecture 1 01 Backpack Problem
This is the most basic backpack problem. Each item can only be placed at most once.
Lecture 2 Complete Knapsack Problem
The second basic knapsack problem model, each item can be placed an infinite number of times.
Lecture 3 Multiple Knapsack Problem
Each item has a fixed maximum number of uses.
Lecture 4: Mixing Three Kinds of Knapsack Problems
Superimpose the previous three simple problems into more complex problems.
Lecture 5: Knapsack problem with two-dimensional costs
A simple common extension.
Lecture 6: Grouped Knapsack Problem
A question type that is also a useful model. The basis for the next two sections.
Lecture 7: Dependent Knapsack Problem
Another way to put restrictions on item selection.
Lecture 8 Generalized Items
The results of my own thinking about the backpack problem are a bit abstract.
Lecture 9: Changes in how to ask the knapsack problem
Try to draw inferences and draw inferences.
———————————-
forward from
xiaoyao_zhang
2. Question analysis
1. Partial Knapsack & Greedy Algorithm
Starting with the features, items can be divided, which means we don’t have to worry about not filling up the backpack. During the segmentation process, grasp the constant quantity, such as – Cost-performance ratio, that is, Wi/Ci, which represents the value of unit weight. So how to release it? Since you don’t have to worry about wasted space or unreasonable arrangements, just sort all the items in descending order of cost-effectiveness and put them into the backpack one by one. When it cannot fit, divide the current items and fill up the remaining space.
①. Greedy algorithm
In this idea, we ensure that every time we put in the items that are currently the most cost-effective, the total value is the greatest. This is the greedy algorithm. The greedy algorithm, as its name suggests, does not consider possible future branches, but focuses on the optimal solution to the current sub-problem. I want the best, no matter if there is something better, it’s that simple.
②. Learn and apply in a practical way
There is such an optimal loading problem: there are N items and a backpack with a capacity of V. The space consumed to put the i-th item is Ci, and each item is equivalent. Find which items can be packed into a backpack to maximize the total value. (Indivisible)
The items here are equivalent, that is to say, Wi/Ci=1/Ci, so the smaller the item, the more cost-effective. Therefore, we can get the following greedy idea: Sort the items in order of space from small to large, and start loading the small ones first. , until the remaining space is insufficient.
2.01 Backpack
Next, let’s go through them in order.
For situations that cannot be divided, the short-sighted greedy algorithm is no longer applicable, and the brute force algorithm of exhaustive calculation will cause the time to exceed the limit. So how to optimize? Infinite enumeration is a kind of search, and optimized search can be done by retaining the historical optimal solution – huh? Dynamic programming!
For details on dynamic programming, please see my [[NOIP1999 Popularization Group] Missile Interception – Longest Non-Ascending Subsequence Problem] Dynamic Planning – CSDN blog article has been read 136 times. The first time I tried dynamic programming dp, I started from the example problem to think hard. The embodiment of mathematical induction in Coding (personal opinion) 
The dynamic transfer equation here is:
dp[i,v]=max(dp[i,v],dp[i?1,v?Ci] + Wi)
Translate: dp[i,v] stores the sub-problem of putting the first i items into a backpack with capacity v. The initial value of dp[i,v] is dp[i-1,v], which is the maximum value after selecting the first i-1 items. When faced with the choice of the i-th item and the current backpack capacity is v, choose 1. If you do not choose this item, the current maximum value is the maximum value after the last judgment and 2. When you select this item, the current value is the maximum value of the remaining capacity distance when the remaining capacity is exactly Ci plus the value of this item after the last selection.
Finally, output dp[N,V]. It is not difficult to conclude that as long as the item information is determined, the answers to all V cases can be obtained through this equation, and finally V output is selected as needed.
3. Complete backpack & multiple backpacks
I only provide one idea here. For other ideas, please refer to the great article (link at the beginning)
All problems are transformed into mathematical problems, all mathematical problems are transformed into algebraic problems, and all algebraic problems are transformed into equation problems – Descartes
All knapsack problems (except some knapsacks) are converted into 01 knapsack problems, and all 01 knapsack problems are converted into dynamic programming problems – MPCBexplorer
For a complete backpack, it can be considered as a 01 backpack that is filled with capacity j and contains at most V/ci items of weight wi, that is, the quantity k <= j/wi. The purpose is achieved by traversing k based on the item selection loop and weight traversal loop.
dp[i][j] = max(dp[i][j],dp[i-1][j-kci] + kwi), 0<=k<=j/ci
Regarding multiple backpacks, the boss has two ideas, one is directly transformed into an 01 backpack, and the other is indirectly transformed into a 01 backpack through a complete backpack. Personally I think the latter is easier to understand.
A complete backpack, isn’t it just a 01 backpack with quantity? Although the number is unlimited, there must be 0<=k<=j/wi, and k actually has a range; the same is true for multiple backpacks, but there are two situations: 1. When the remaining space is enough, 0<=k<=mi ; 2. When there are enough items, 0<=k<=j/wi - you see, there is just one more condition for the upper limit of taking items with enough space! When deciding specifically which one is the upper limit in the program, take
Ki=min(num[i],j/ci)
That’s it, and then there’s the complete backpack idea above:dp[i][j] = max(dp[i][j],dp[i-1][j-kci] + kwi)< /strong>
3. Upload the code
1. Part of the backpack
program part_bag;
var
n,i:longint;
v,ans:real;
a,c,w:array[1..10000] of real;
// Sort by cost performance
//Steal a quick change in the system file
//Quick sort: a sort based on binary search method
procedure sort(l,r: longint);
var
i,j: longint;
x,y:real;
begin
i:=l;
j:=r;
x:=a[(l + r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=c[i];
c[i]:=c[j];
c[j]:=y;
y:=w[i];
w[i]:=w[j];
w[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
//Quantity, size
read(n,v);
for i:=1 to n do
begin
// size, value
read(c[i],w[i]);
//price/performance ratio
a[i]:=w[i]/c[i];
end;
sort(1,n);
//DEBUG debugging: cost-effectiveness after output sorting
//for i:=1 to n do writeln(a[i]:0:2);
i:=n;
//When there is enough space
while v>=c[i] do
begin
//Greedy: load all
ans:=ans + w[i];
v:=v-c[i];
dec(i);
end;
//Split the last item
ans:=ans + w[i]*(v/c[i]);
writeln(ans:0:2);
end.
Enter #1
4 50↙
10 60↙
20 100↙
30 120↙
15 45↙Output #1
240.00
2.01 Backpack
program o1_bag;
var
n,v,i,j,best:longint;
c,w:array[1..10000] of longint;
//Note that the subscript starts from 0
dp:array[0..10000,0..10000] of longint;
//Function to get the maximum value
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
begin
read(n,v);
for i:=1 to n do read(c[i],w[i]);
//i: in the first i items
for i:=1 to n do
//j: When the remaining capacity is j
for j:=0 to v do
begin
//No matter whether the remaining space is enough or not, at least there is
dp[i,j]:=dp[i-1,j];
//When there is enough remaining space
if j>=c[i] then dp[i,j]:=max(dp[i-1,j-c[i]] + w[i],dp[i,j]);
end;
best:=0;
//Find the maximum value output
for j:=1 to v do
if dp[n,j]>best then best:=dp[n,j];
writeln(best);
end.
Enter #1
4 5
↙
1 2↙
2 4↙
3 4↙
4 5↙Output #1
8
3. Complete backpack
program completed_bag;
var
n,v,i,j,k,best:longint;
c,w:array[1..10000] of longint;
//Note that the subscript starts from 0
dp:array[0..10000,0..10000] of longint;
//Function to get the maximum value
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
begin
read(n,v);
for i:=1 to n do read(c[i],w[i]);
//i: in the first i items
for i:=1 to n do
//j: When the remaining capacity is j
for j:=0 to v do
begin
//No matter whether the remaining space is enough or not, at least there is
dp[i,j]:=dp[i-1,j];
for k:=0 to j div c[i] do
//When there is enough remaining space
if j>=k*c[i] then dp[i,j]:=max(dp[i-1,j-k*c[i]] + k*w[i],dp[i,j]);
end;
best:=0;
//Find the maximum value output
for j:=1 to v do
if dp[n,j]>best then best:=dp[n,j];
writeln(best);
end.
Enter #1
4 5↙
1 2↙
2 4↙
3 4↙
4 5↙Output #1
10
4. Multiple backpacks
program numbers_of_bags;
var
n,v,i,j,k,best:longint;
c,w,m:array[1..10000] of longint;
//Note that the subscript starts from 0
dp:array[0..10000,0..10000] of longint;
//Function to get the maximum value
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
//Function to get the minimum value
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;
begin
read(n,v);
for i:=1 to n do read(c[i],w[i],m[i]);
//i: in the first i items
for i:=1 to n do
//j: When the remaining capacity is j
for j:=0 to v do
begin
//No matter whether the remaining space is enough or not, at least there is
dp[i,j]:=dp[i-1,j];
for k:=0 to min(m[i],j div c[i]) do
//When there is enough remaining space
if j>=k*c[i] then dp[i,j]:=max(dp[i-1,j-k*c[i]] + k*w[i],dp[i,j]);
end;
best:=0;
//Find the maximum value output
for j:=1 to v do
if dp[n,j]>best then best:=dp[n,j];
writeln(best);
end.
Enter #1
3 7↙
2 3 12↙
2 5 15↙
1 2 3↙Output #1
17
4. Conclusion
When explaining the greedy algorithm from the perspective of the knapsack problem, I didn’t expect that the protagonist turned out to be dynamic programming. Greedy is an entry-level algorithm that should be mastered; however, it will not appear frequently in the future. After all, dynamic programming is the king, and greed is always easy to miss the optimal solution.
The poem says:
The screen is filled with absurd words and a handful of bitter tears.
They are all crazy about coders, who can explain their hatred!
If there are any bugs in the code, please point them out, thank you!
I’m so exhausted! Finished the first draft at 23:31!
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57530 people are learning the system