C++

C++ – Basic knapsack problem

XU

Question description

Chenchen is a talented child, and 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 are Chenchen, you can complete this task ?

Input and output format

Input format

The first line has 22 integers T(1 \le T \le 1000)T(1≤T≤1000) and M(1 \le M \le 100)M(1≤M≤100), separated by a space , TT represents the total time that can be used to collect herbs, and MM represents the number of herbs in the cave. Each of the following MM 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.

Output format

1 integer, indicating the maximum total value of the herbs that can be collected within the specified time.

Sample

Sample input

70 3
71 100
69 1
1 2

Sample output:

3

(ps; title source is Luogu p1048)

answer

This is a standard knapsack problem. Knapsack is a common type of problem in dynamic programming. The basic idea is to seek the maximum benefit within the specified capacity/total price/time constraints. Its recursive formula is roughly

if(j>s[i].s) dp[i][j]=max(dp[i-1][js[i].s]+s[i].v,dp[i-1][ j]) else dp[i][j]=dp[i-1][j]; (ps: s[i].s represents the space occupied by the i-th item, s[i].v represents its value. dp[i][j] represents the maximum total price when the backpack size is j. i represents the current Determining whether to load items into the backpack. Therefore, dp[n][m] is the maximum value. ) The code is as follows; (ps; this code adds a part that outputs the list of selected items.)

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node {
    int v, s;
};
node va[101];
int dp[103][1100];
int main() {
    int c, n;
    scanf("%d %d", &c, &n);
    int tem[n];
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &va[i].s, &va[i].v);
    for(int i = 1; i <= n; i++)
        //初始化dp[i][j]便于之后比较。
        dp[i][0] = 0;
    for(int j = 0; j <= c; j++)
        dp[0][j] = 0;
    for(int i = 1; i <= n; i++) {
        //双重循环遍历每个位置。
        for(int j = 0; j <= c; j++) {
            if(va[i].s > j)
                //判断当前背包是否能装下第i件物品。
                dp[i][j] = dp[i - 1][j];
            else {
                if(dp[i - 1][j - va[i].s] + va[i].v > dp[i - 1][j])
                    //对比装了物品前后的总价值取最大的。
                    dp[i][j] = dp[i - 1][j - va[i].s] + va[i].v;
                else dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n][c] << endl;
    //输出最大值。
    for(int i = 1; i <= n; i++) tem[i] = 0;
    int j = c;
    for(int i = n; i > 0; i--) {
        if(dp[i][j] > dp[i - 1][j]) {
            tem[i] = 1;
            j = j - va[i].s;
        }
    }
    for(int i = 1; i <= n; i++)
        if(tem[i] == 1) cout << i << ' ';
    return 0;
}
/*附样例输入
15 5
2 6
2 3
6 5
5 4
4 6*/
/*表格输出方便研究。
  0__1__2__3__4__5__6__7__8__9_10_11_12_13_14_15
0!0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0!
1!0  0  6  6  6  6  6  6  6  6  6  6  6  6  6  6!
2!0  0  6  6  9  9  9  9  9  9  9  9  9  9  9  9!
3!0  0  6  6  9  9  9  9 11 11 14 14 14 14 14 14!
4!0  0  6  6  9  9  9 10 11 13 14 14 14 15 15 18! 
5!0  6  6  9  9 12 12 15 15 15 16 17 19 20 20 20! */

Post Reply