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;
}

空间优化版本：

#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;
}