7-2 拼题A打卡奖励 (25 分) 特殊的01背包

拼题 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 枚金币。

思路：（dp自上而下）

显然这是一个01背包问题。但是，按照常规的想法，把时间看成是物品的体积,金币看成是价值，则 M 就是背包的容量。但是根据题目的数据范围， M（≤365×24×60）M（≤365×24×60） ,复杂度 NM 肯定会TLE。

我们再看一下题目给定其他数据范围，显然 ci<30 成为题目转化的一个突破口。按照原来做法就是用最小容量求最大价值，现在反过来用最大价值求最小容量。最大价值：1000∗30, 复杂度：1000∗30∗1000 。

#include
#include
using namespace std;
const int M = 365*24*60, N = 1010;
int a[N],w[N];
int dp[30011];// i金币 dp[i]时间 
int main(){memset(dp,0x3f,sizeof(dp));dp[0] = 0;int n,m,sum = 0;cin>>n>>m; for(int i = 1; i <= n; i++) cin>>a[i];for(int i = 1; i <= n; i++) {cin>>w[i];sum += w[i];}for(int i = 1; i <= n; i++){for(int j = sum; j >= w[i]; j--){// dp自上而下if(dp[j] > dp[j-w[i]] + a[i]){dp[j] = dp[j-w[i]] + a[i];}}}for(int i = sum; i >= 0; i--){if(dp[i] <= m) {cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！