Strange Lunchbox题解

题目链接：Strange Lunchbox

题意：

给定n个便当盒，每个盒子中有ai数量的A和bi数量的B。问是否能找到m个盒子，使得A和B的数量总和，分别至少达到x和y。如果可以输出数量，否则输出-1。

思路：

• 简单的01背包问题， 我们可以把x和y视为两个容量分别为x和y的书包，每次加入餐盒就占用ai和bi的空间，看最后是否能占满空间。
• 用f[i] [j]表示当A容量为i，B容量为j时，此时包中的盒子数量。
• 盒子从开头开始遍历，而两个书包各自从容量x和y开始逆序遍历。
• **第一个问题：为什么可以逆序遍历书包容量？**我们首先可以将所有容量的书包初始化为一个极大值，当我们逆序遍历书包容量时，如果上一个状态还没有达到，那么说明当前状态也不可达，所以可以逆序遍历。
• **第二个问题，为什么要逆序遍历？**如果正常从0开始遍历也是可以的，但是要多占用1维空间来代表前k个盒子。显然在题目范围比较大时容易超出空间限制。

三维AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int N = 300 + 10,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

vector<PII>p;
int n,x,y;
int f[N][N][N];//f[i][j]表示x容量为i,y容量为j时的数量

int main()
{
	cin >> n >> x >> y;
	
	p.push_back({ 0, 0 });
	for(int i=1;i<=n;++i)
	{
		PII a;
		cin >> a.first >> a.second;
		p.push_back(a);
	}

	memset(f, 0x3f, sizeof(f));
	for (int i = 0; i <= n; ++i)f[i][0][0] = 0;
	for (int k = 1; k <= n; ++k)
	{
		for(int i=0;i<=x;++i)
			for (int j = 0; j <= y; ++j)
				f[k][i][j] = min(f[k-1][i][j], f[k - 1][max(0,i-p[k].first)][max(0,j-p[k].second)] + 1);
	}

	f[n][x][y] == INF ? printf("-1") : printf("%d", f[n][x][y]);

	return 0;
}

二维AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int N = 300 + 10,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

vector<PII>p;
int n,x,y;
int f[N][N][N];//f[i][j]表示x容量为i,y容量为j时的数量

int main()
{
	cin >> n >> x >> y;
	
	p.push_back({ 0, 0 });
	for(int i=1;i<=n;++i)
	{
		PII a;
		cin >> a.first >> a.second;
		p.push_back(a);
	}

	memset(f, 0x3f, sizeof(f));
	for (int i = 0; i <= n; ++i)f[i][0][0] = 0;
	for (int k = 1; k <= n; ++k)
	{
		for(int i=0;i<=x;++i)
			for (int j = 0; j <= y; ++j)
				f[k][i][j] = min(f[k-1][i][j], f[k - 1][max(0,i-p[k].first)][max(0,j-p[k].second)] + 1);
	}

	f[n][x][y] == INF ? printf("-1") : printf("%d", f[n][x][y]);

	return 0;
}