Acwing - the collection of pet elves - (multidimensional 01 Backpack + positive and reverse order + two forms of DP for the answer)

The collection of pet elves

The question ：
There is n A pet , Catch them to a Physical strength and b Spirit ball of . Now you have m physical strength ,k An elf ball . Ask how many pets you can catch at most , Then when there are most pets , How much physical strength is left at most .

reflection ：
Obviously, this can also optimize the dimension of enumerating items . Then triple cycle is ok . For enumeration h When , Reverse order and positive order are the same , Because the last layer m It's in reverse order , therefore h Even positive order , He also uses the upper layer every time , Not on this floor . If there is 4 Layer circulation , equally , Just one layer in reverse order . For those who require the most pets , Highest physical strength . Then just enumerate directly , Find out more pets , If the same, then look at the least physical use . although dp The definition of , I can't directly ask how much physical strength I can have left , But you can ask how much physical strength you used, right .
The second way , It's the gold coin title of the robot competition before . For example, the classic backpack volume and value , Just exchange the power of value and volume , Let what you ask be what you maintain , The result is known , Finally, enumerate and judge dp Whether the status inside meets the given limit is ok . So this question can define the state dp[i][j], Not more than i HP , Captured j A pet , At least how many elf balls should be used . Then finally enumerate all the States , See if < The number of ELF balls , If you can, you can update the answer . The same is true dp[i][j] Defined as , No more than i Spirit ball of , Captured j A pet , How much physical strength should be used at least . Then do the same .
How to determine the state
Namely ：
1. Put the required answer , Become dp The answer , This is the most common way .
2. Put the required answer , Put it in dp In the defined state , and dp The answer is a known condition .
For how to define the state , It depends on the scope of each limitation , See how many cycles you can use at least , Try to choose the one with the best time complexity . But we must ensure that there is an optimal substructure to deal with .
Another thing worth noting is , Generally, the first dimension enumeration items are optimized ,dp The state of is the value of the upper layer every time , So don't consider not choosing i The emptying of this item . Actually, I have considered . But if it is not optimized , Then you have to go , Otherwise, there will be less updates . It must be from 1 To m All have to enumerate , Can't fall .

 Not more than j Spirit ball and not super k Physical strength , How many pets can you catch at most .

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;

int T,n,m,k,h;
PII va[110];
int dp[1010][510];

signed main()
{
    
	IOS;
	cin>>m>>h>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=m;j>=1;j--)
		{
    
			for(int k=1;k<=h;k++)
			{
    
				if(j>=va[i].fi&&k>=va[i].se)
				dp[j][k] = max(dp[j][k],dp[j-va[i].fi][k-va[i].se]+1);
			}
		}
	}
	int maxn = 0,sum = 0;
	for(int k=0;k<h;k++)
	{
    
		if(maxn<dp[m][k])
		{
    
			maxn = dp[m][k];
			sum = h-k;
		}
		else if(maxn==dp[m][k]) sum = max(sum,h-k);
	}
	cout<<maxn<<" "<<sum<<"\n";
	return 0;
}

 Not more than j Physical strength and grasp k Our pet , At least how many elf balls to use .

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;

int T,n,m,k,h;
PII va[110];
int dp[510][110];

signed main()
{
    
	IOS;
	cin>>m>>h>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	mem(dp,0x3f);
	for(int i=0;i<=h;i++) dp[i][0] = 0;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=h;j>=1;j--)
		{
    
			for(int k=1;k<=n;k++)
			{
    
				if(j>=va[i].se)
				dp[j][k] = min(dp[j][k],dp[j-va[i].se][k-1]+va[i].fi);
			}
		}
	}
	int maxn = -inf,sum = 0;
	for(int i=0;i<h;i++)
	{
    
		for(int j=0;j<=n;j++)
		{
    
			if(dp[i][j]<=m)
			{
    
				if(maxn<j)
				{
    
					maxn = j;
					sum = h-i;
				}
				else if(maxn==j) sum = max(sum,h-i);
			}
		}
	}
	cout<<maxn<<" "<<sum<<"\n";
	return 0;
}

 Not more than j The elf ball and caught k Our pet , How much physical strength should we use at least .
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;

int T,n,m,k,h;
PII va[110];
int dp[1010][110];

signed main()
{
    
	IOS;
	cin>>m>>h>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	mem(dp,0x3f);
	for(int i=0;i<=m;i++) dp[i][0] = 0;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=m;j>=1;j--)
		{
    
			for(int k=1;k<=n;k++)
			{
    
				if(j>=va[i].fi)
				dp[j][k] = min(dp[j][k],dp[j-va[i].fi][k-1]+va[i].se);
			}
		}
	}
	int maxn = -inf,sum = 0;
	for(int i=0;i<=m;i++)
	{
    
		for(int j=0;j<=n;j++)
		{
    
			if(dp[i][j]<h)
			{
    
				if(maxn<j)
				{
    
					maxn = j;
					sum = h-dp[i][j];
				}
				else if(maxn==j) sum = max(sum,h-dp[i][j]);
			}
		}
	}
	cout<<maxn<<" "<<sum<<"\n";
	return 0;
}

Robot gold coin topic :

reflection ：
If you follow the normal way of thinking, it is dp[i][j] Before use i Card roll , No more than j Time for , How many gold coins can you get at most . But such a double cycle must have timed out . But the scope of finding gold coins is very small . therefore dp[i][j] Defined as before i Card roll , Get no more than j Gold coins , At least how much time . Finally, just enumerate the answer of gold coin , On the premise that the time does not exceed the conditions .

Code ：

 2D version ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
PII va[N];
int dp[1010][30010];

signed main()
{
    
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i].fi;
	for(int i=1;i<=n;i++) cin>>va[i].se;
	int R = n*30;
	mem(dp,0x3f);
	for(int i=0;i<=n;i++) dp[i][0] = 0;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<=R;j++)
		{
    
			dp[i][j] = min(dp[i][j],dp[i-1][j]); // Note that this is a double cycle. You can't throw it away , If you optimize a single loop , Then itself is already on the next level , So don't write anymore , But it needs to be updated here . It must be from 1 To R, Cannot from va[i].se Start , Because there will be less .
			if(j>=va[i].se)
			dp[i][j] = min(dp[i][j],dp[i-1][j-va[i].se]+va[i].fi);
		}
	}
	int maxn = 0;
	for(int i=1;i<=R;i++)
	{
    
		if(dp[n][i]<=m)
		maxn = max(maxn,i);
	}
	cout<<maxn;
	return 0;
}

 One dimensional version ：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
PII va[N];
int dp[30010];

signed main()
{
    
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i].fi;
	for(int i=1;i<=n;i++) cin>>va[i].se;
	int R = n*30;
	mem(dp,0x3f);
	dp[0] = 0;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=R;j>=va[i].se;j--) // because dp Itself is the upper layer , So here from va[i].se It's okay at first .
		dp[j] = min(dp[j],dp[j-va[i].se]+va[i].fi);
	}
	int maxn = 0;
	for(int i=1;i<=R;i++)
	{
    
		if(dp[i]<=m)
		maxn = max(maxn,i);
	}
	cout<<maxn;
	return 0;
}

summary ：
Think more , Understand the essence of Algorithm .