Skip to main content

One post tagged with "背包问题"

View All Tags

· 4 min read
Wei Junyu

题目来源：2022年团体程序设计天梯赛-模拟赛：L3-2 拼题A打卡奖励 (30 分)

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

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

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

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

输入样例：

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

输出样例：

40

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

解​

当时人傻的啊，一眼看上去就是个普通的01背包问题。于是看了看时间大小：365×24×60=525600365×24×60=525600？？？

数组开那么大很危险吧？？？不信邪，提交得7分。不管怎么优化，都是寄。

花费的时间可能会1年，枚举时间太不现实了。题目说了，可获得的金币数量非常少，于是换了一种dp思路。

dp[i] = x 表示：当金币数量为 i 时，需要的最少时间 x。

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int t[N], c[N]; // 时间和金钱
int dp[40 * N], mxv;

int main() {
    freopen("1.txt", "r", stdin);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> t[i];
    for (int i = 1; i <= n; i ++) {
        cin >> c[i];
        mxv += c[i]; // 记录能获得的最大金币数量
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = mxv; j >= c[i]; -- j) {
            dp[j] = min(dp[j], dp[j - c[i]] + t[i]);
        }
    }

    for (int i = mxv; i >= 0; i --) {
        // 从最大金币数量向下搜索
        // 找到第一个满足时间条件的金币数量
        if (dp[i] <= m) {
            cout << i;
            break;
        }
    }

    return 0;
}