7-2 拼题A打卡奖励 dp

7-2 拼题A打卡奖励
分数 25
作者 陈越
单位 浙江大学
拼题 A 的教超搞打卡活动，指定了 N 张打卡卷，第 i 张打卡卷需要 m
i
​
分钟做完，完成后可获得 c
i
​
枚奖励的金币。活动规定每张打卡卷最多只能做一次，并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币？

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

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

输入样例：
5 110
70 10 20 50 60
28 1 6 18 22
输出样例：
40
样例解释：
选择最后两张卷子，可以在 50+60=110 分钟内获得 18+22=40 枚金币。

#include<bits/stdc++.h>
using namespace std;
const int N=1004;
const int INF=0x3f3f3f3f;
int n,m;
int w[N],v[N];
//int f[N][10000];
int dp[N][30005];//前i个物品中得到价值为j时候的最小花费 //ans为dp[n][j]<m时最大的j 
int mv=0;

int main()
{
//	cout<<365*60*24;
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>w[i];
	for(int i=1;i<=n;++i){
		cin>>v[i];
		mv+=v[i];
	}

// 01背包写法，空间不够，而且也会超时，因为“花费”这一维度规模比较大，而递推时需要一一枚举
//		for(int i=1;i<=n;++i)
//		for(int j=0;j<=m;++j)
//		{
//			if(j>=w[i])
//			f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
//			else f[i][j]=f[i-1][j];
//		}
		

//下面是另一种思路，第二维换成价值
		//初始化 
		for(int i=0;i<=n;++i)
		{
			for(int j=0;j<=mv;++j){
				
				dp[i][j]=INF; 
			}
		}
		dp[0][0]=0;
		//递归过程：分为取第i个和不取第i个
		for(int i=1;i<=n;++i)
		{
			for(int j=0;j<=mv;++j){
				if(j>=v[i])//注意边界
				dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
				else 
				dp[i][j]=dp[i-1][j];
			}
		}
		//可以改进递推过程：由于递归方程中两个来源都是上一个i的,去掉第一个维度,节省空间，注意这时候j要从大到小迭代，才能保证递推过程中的dp[j-v[i]]是来源于i-1而不是i
// 		for(int i=1;i<=n;++i)
// 		{
// 			for(int j=mv;j>=0;--j)
// 			{
// 				if(j>v[i])
// 				dp[j]=min(dp[j-v[i]]+w[i],dp[j]);
// 				else 
// 				dp[j]=dp[j];
// 		}
		//取答案：最小花费在给定的m内的最大价值
		for(int j=mv;j>=0;j--)
		{
			if(dp[n][j]<=m){
				cout<<j;
				break;
			}
		}

//	cout<<f[n][m];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

空间优化版本：

#include<bits/stdc++.h>
using namespace std;
const int N=1004;
const int INF=0x3f3f3f3f;
int n,m;
int w[N],v[N];

int dp[30005];//前i个物品中得到价值为j时候的最小花费 //ans为dp[n][j]<m时最大的j 
int mv=0;

int main()
{
//	cout<<365*60*24;
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>w[i];
	for(int i=1;i<=n;++i){
		cin>>v[i];
		mv+=v[i];
	}

		for(int j=0;j<=mv;++j){
				
				dp[j]=INF; 
		}
		dp[0]=0;
		

		for(int i=1;i<=n;++i)
		{
			for(int j=mv;j>=0;--j)
			{
				if(j>=v[i])
				dp[j]=min(dp[j-v[i]]+w[i],dp[j]);
				else 
				dp[j]=dp[j];
			}
		}
		//取答案：最小花费在给定的m内的最大价值
		for(int j=mv;j>=0;j--)
		{
			if(dp[j]<=m){
				cout<<j;
				break;
			}
		}

//	cout<<f[n][m];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49