Knapsack problem in dynamic programming (01 Knapsack)

Introduction:

A long time ago, there was a king who owned five gold mines. Each gold mine had different gold reserves and required a different number of workers to participate in the excavation. For example, some gold mines have a reserve of 500kg of gold and require 5 workers to dig; some gold mines have a reserve of 200kg of gold and require 3 workers to dig… If the total number of workers participating in mining is 10. Every gold mine must be dug or none. You cannot send half the people to dig half of the gold mine. It is required to use a program to find out which gold mines should be mined in order to get as much gold as possible?

I thought of a way! We can sort the gold mines according to their cost-effectiveness from high to low, giving priority to the gold mines with the highest cost-effectiveness to mine, and then the second most cost-effective gold mines…

According to this idea, gold mines are ranked from high to low in terms of cost performance, and the ranking results are as follows. The first place is a gold mine with 350kg of gold/3 people, and the per capita output value is about 116.6kg of gold. The second place is a gold mine with 500kg gold/5 people, and the per capita output value is 100kg gold. The third place is a gold mine with 400kg gold/5 people, and the per capita output value is 80kg gold. No. 4, a gold mine with 300kg gold/4 people, the per capita output value is 75kg gold. No. 5, a gold mine with 200kg gold/3 people, the per capita output value is about 66.6kg gold. Since the number of workers is 10, after giving priority to digging the gold mines ranked first and second in terms of cost performance, there are still 2 workers left, which is not enough to dig other gold mines. Therefore,the final optimal gold mine profit is 350 + 500 or 850kg of gold!

If you give up the most cost-effective gold mine of 350kg gold/3 people and choose the 500kg gold/5 people and 400kg gold/5 people gold mines, the total profit is 900kg gold. Is it greater than the 850kg gold you get?

Solution:

The king first came to the location of the fifth gold mine. His ministers told him that if you want to dig the fifth gold mine, you will need 5 people, and the fifth gold mine can dig out 500 kilograms of gold. The king laughed loudly when he heard this, because he originally thought that it would be a difficult question to know how much gold could be dug out of 5 gold mines with only 10 people. However, after listening to him just now, When the minister said that, the king already knew the maximum amount of gold that could be dug out. How did the king know the maximum amount of gold that could be dug out without knowing about other gold mines? His ministers did not know this mystery either, so his ministers asked him: “Your Majesty, the wisest king, we have not told you about other gold mines, how do you know the final answer?

The king continued: “If I dig the fifth gold mine, then I can get 500 kilograms of gold now, and I will use 5 people, then I will have 5 people left. My dear left subordinate, if you tell If I leave all the remaining 5 people and all the other gold mines to you to mine, how much gold can you dig out for me at most? Then I will know that I will definitely mine the 5th gold mine. What is the maximum number of gold coins that can be obtained under the circumstances?”

The king smiled and continued to say to his right subordinate: “Dear right subordinate, maybe I don’t intend to mine this fifth gold mine, then I still have 10 people. If I combine these 10 people and the remaining gold If I give you all the mines, how much gold can you dig out for me at most?”

The king’s right man said wisely: “Dear Your Majesty, I understand what you mean.If I answer that I can buy and mine at most y gold, then you can choose between y and x + 500 A larger one, and this larger one is the maximum number of gold coins we can get in the end. Do you think I understand this correctly?”

Example 1: 2224: The King’s Gold Mine

The king discovered n gold mines in his country. For the convenience of description, we number them from 1 to n.

For the i-th gold mine, w(i) manpower needs to be invested to dig out V(i) units of gold.

Now the king wants to dig these gold mines, but only M manpower can be used to invest at most. How many units of gold can be dug out at most.

1 <= N, M <= 200
1 <= v(i) <= 3000

Input format

There are two integers in the first line, N and M respectively.

The next N lines have two integers in each line, and the i + 1th line contains w(i) and v(i).

Output format

Each line contains an integer, which is the maximum number of units of gold that can be mined.

Input sample

Output sample

analyze:

Suppose there are n items and a backpack with a capacity of V. The cost of the i-th item is w[i], and the value is c[i]. f[i][v] means that the first i item is put into a backpack with a capacity of v. The maximum value that the backpack can obtain, then we can easily analyze the calculation method of f[i][v],

(1) In the case of v
f[i][v]=f[i-1][v]

(2) In the case of v>=w[i], the backpack capacity can hold the i-th item, and we have to consider whether we can obtain greater value by taking this item.

If taken, f[i][v] = f[i-1][v-w[i]] + c[i]. Here f[i-1][v-w[i]] + c[i] refers to the maximum value when i-1 items are taken into account and the backpack capacity is v-w[i], which is also equivalent to the i-th item. The space of w[i] is freed up. If you don’t take it, f[i][v] = f[i-1][v], whether to take it or not take it, naturally compare the two situations which one has the greatest value.

include <bits/stdc + + .h>
using namespace std;
int n,m,w[1001],v[1001],dp[1001][1001];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i + + )
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i + + )
        for(int j=1;j<=m;j + + )
            if(j>=w[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
            else dp[i][j]=dp[i-1][j];
    cout<<dp[n][m];
    return 0;
}

Example 2: 2463: Collecting herbs

Title description

Shang Ziye is a talented child. His dream is to become the greatest doctor in the world. To this end, he wanted to become a disciple of the most prestigious doctor nearby. In order to judge his qualifications, the doctor gave him a difficult problem. The doctor took him to a cave full of medicinal herbs and said to him: “My child, there are some different herbs in this cave. It takes some time to collect each one, and each one has its own value. I will give You have a period of time, during which time you can collect some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you collect.”
If you were Shang Ziye, could you complete this task?

Input format

The first line of each set of input data contains two integers T (1<=T<=1000) and M (1<=M<=100), separated by a space. T represents the total time that can be used to collect herbs. , M represents the number of herbs in the cave. Each of the next M lines includes two integers between 1 and 100 (including 1 and 100), which respectively represent the time of picking a certain herb and the value of this herb.
Data size:
For 30% of the data, M<=10;
For all data, M<=100.

Output format

Each set of output includes one line, and this line contains only one integer, indicating the maximum total value of the herbs that can be collected within the specified time.

Input sample

Output sample

How to adjust the test data range to: T (1 <= T <= 10000) and M (1 <= M <= 10000). Define a two-dimensional array int dp[10000][10000] in this way to exceed the memory limit in the program!

The time and space complexity of the above method are both O(N*V). The time complexity can basically no longer be optimized, but the space complexity can be optimized to O(V). First consider how to implement the basic idea mentioned above. There must be a main loop i=1..N, and each time all the values of the two-dimensional array f[i][0..V] are calculated. So, if only one array f[0..V] is used, can it be guaranteed that after the i-th loop ends, f[v] represents the state f[i][v] we defined? f[i][v] is derived recursively from the two sub-problems f[i-1][v] and f[i-1][v-w[i]]. Can we ensure that f[i][v ] can we get the values of f[i-1][v] and f[i-1][v-w[i]]? In fact, this requires us to push f[v] in the reverse order of v=V..0 in each main loop, so as to ensure that when f[v] is pushed, f[v-w[i]] saves the state f[i -1][v_x0002_w[i]] value.

#include <bits/stdc + + .h>
using namespace std;
int dp[10001],w[10001],v[10001],n,m;
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i + + )
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i + + )
        for(int j=m;j>=w[i];j--)
            dp[j]=max(dp[j-w[i]] + v[i],dp[j]);
    cout<<dp[m];
    return 0;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56997 people are learning the system