7-2 punch in reward DP for puzzle a

7-2 Puzzle A Punch in reward
fraction 25
author Chen Yue
Company Zhejiang University
Puzzle A Our teachers engage in punch in activities , It specifies N Punch in roll , The first i A punch in paper needs m
i
​
Minutes to finish , After completion, you can get c
i
​
A gold coin for reward . The activity stipulates that each punch in paper can only be done once at most , And it is not allowed to hand in the papers in advance . The total duration of the activity is M minute . Please figure out how many gold coins you can win at most ？

Input format ：
Input first gives two positive integers in the first line N（≤10
3
） and M（≤365×24×60）, Corresponding to the number of punch cards and the number of punch cards “ minute ” Total activity duration in （ No more than a year ）. The next line shows N The time it takes to punch in a paper m
i
​
（≤600）, The last line gives N The number of bonus gold coins corresponding to each punch in roll c
i
​
（≤30）. The above are positive integers , Numbers in a line are separated by spaces .

Output format ：
Output the maximum number of gold coins you can win in one line .

sample input ：
5 110
70 10 20 50 60
28 1 6 18 22
sample output ：
40
Sample explanation ：
Choose the last two papers , Can be in 50+60=110 Get... In minutes 18+22=40 Gold coins .

#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];// front i The value obtained from items is j The minimum cost of time  //ans by dp[n][j]<m The biggest 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 Backpack writing , Space is not enough , And it will time out , because “ cost ” This dimension is relatively large , And the recursion needs to enumerate one by one 
// 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];
// }
		

// Here is another idea , The second dimension is replaced by value 
		// initialization  
		for(int i=0;i<=n;++i)
		{
    
			for(int j=0;j<=mv;++j){
    
				
				dp[i][j]=INF; 
			}
		}
		dp[0][0]=0;
		// A recursive process ： It is divided into two parts i A sum does not take the first i individual 
		for(int i=1;i<=n;++i)
		{
    
			for(int j=0;j<=mv;++j){
    
				if(j>=v[i])// Pay attention to the border 
				dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
				else 
				dp[i][j]=dp[i-1][j];
			}
		}
		// The recursive process can be improved ： Because both sources in the recursive equation are the previous one i Of , Remove the first dimension , Save a space , Pay attention to this time j Iterating from large to small , In order to ensure the dp[j-v[i]] It comes from i-1 instead of 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];
// }
		// Take the answer ： The minimum cost is given m Maximum value within 
		for(int j=mv;j>=0;j--)
		{
    
			if(dp[n][j]<=m){
    
				cout<<j;
				break;
			}
		}

// cout<<f[n][m];
	return 0;
}

Space optimized version ：

#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];// front i The value obtained from items is j The minimum cost of time  //ans by dp[n][j]<m The biggest 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];
			}
		}
		// Take the answer ： The minimum cost is given m Maximum value within 
		for(int j=mv;j>=0;j--)
		{
    
			if(dp[j]<=m){
    
				cout<<j;
				break;
			}
		}

// cout<<f[n][m];
	return 0;
}