摘要
Title: L3-2 拼题A打卡奖励 (30 分)
Tag: 01背包
Memory Limit: 64 MB
Time Limit: 1000 ms

L3-2 拼题A打卡奖励 (30 分)

题意

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

可以发现背包的容量很大，但是获利比较少，所以可以采用01背包的逆过程

可以把获利看作背包容量，把原来的背包容量当作获利
也就是我们要求，在当前获利下，最少需要的背包容量是多少？
最后按照获利的总数逆序遍历，找到第一个体积容量小于等于背包容量的获利，就是答案

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-18 22:03:11
* @FilePath: \ACM\GPLT\2022MoNi\L3-02.CPP
* @LastEditTime: 2022-04-18 22:50:42
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e4, M = 1e5;
int dp[M], v[N], w[N];

signed main()
{
    int n, m, sum = 0;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &v[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &w[i]), sum += w[i];

    memset(dp, 0x3f, sizeof dp); //由于是求最小值，所以将数组变为无穷大
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = sum; j >= w[i]; --j)
        {
            dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    for (int i = sum; i >= 0; --i)
    {
        if (dp[i] <= m)
        {
            printf("%lld", i); // 输出最多获利
            return 0;
        }
    }
    return 0;
}

L3-2 拼题A打卡奖励 (30 分)

题意

思路

代码