7-2拼题A打卡奖励(25分)【01背包】【2021 RoboCom 世界机器人开发者大赛-本科组（复赛）】

7-2 拼题A打卡奖励(25分)

拼题 A 的教超搞打卡活动，指定了 N 张打卡卷，第 i 张打卡卷需要 mi​ 分钟做完，完成后可获得 ci​ 枚奖励的金币。活动规定每张打卡卷最多只能做一次，并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币？

输入格式：

输入首先在第一行中给出两个正整数 N（≤103） 和 M（≤365×24×60），分别对应打卡卷的数量和以“分钟”为单位的活动总时长（不超过一年）。随后一行给出 N 张打卡卷要花费的时间 mi​（≤600），最后一行给出 N 张打卡卷对应的奖励金币数量 ci​（≤30）。上述均为正整数，一行内的数字以空格分隔。

输出格式：

在一行中输出最多可以赢得的金币数量。

输入样例：

5 110
70 10 20 50 60
28 1 6 18 22

输出样例：

40

样例解释：

选择最后两张卷子，可以在 50+60=110 分钟内获得 18+22=40 枚金币。

编译器

NO_COMPILER

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 30010;
int n, m, v[N], w[N], dp[M];  //装到价值为i时，需要的背包的最小容量是dp[i] 

int main(){
    cin >> n >> m;
    int sum = 0;  //不用sum，替换为30000也能ac 
    for(int i = 1; i <= n; i++) cin >> w[i];  //耗时 
    for(int i = 1; i <= n; i++) cin >> v[i], sum += v[i];  //金币 
    memset(dp, 127, sizeof dp);//用最大价值求最小容量,初始化成最大
    dp[0] = 0;  //边界，0价值用掉0容量
    for(int i = 1; i <= n; i++)  //先遍历物品
        for(int j = sum; j >= v[i]; j --)  //再遍历背包容量：背包容量是金额 
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
    int i;
    for(i = sum; i >= 0; i--)
        if(dp[i] <= m) break;
    cout << i;
    return 0;
}

编译器输出

测试点	结果	测试点得分	耗时	内存
0	答案正确	12	4.00 ms	2500 KB
1	答案正确	1	5.00 ms	2632 KB
2	答案正确	1	5.00 ms	2488 KB
3	答案正确	1	16.00 ms	2500 KB
4	答案正确	2	28.00 ms	2368 KB
5	答案正确	4	16.00 ms	2492 KB
6	答案正确	4	16.00 ms	2496 KB

评测结果 答案正确(25 分)