潜水员要潜水，给出n个气缸（1<=n<=1000），每个气缸中有氧气量为ti，氮气量为ai，气缸重量为wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）。现在潜水员需要量为t的氧气，量为a的氮气（1<=t<=21，1<=a<=79），问选哪些气缸，使得重量最小。
【背包】二维背包问题，不同的是这个要选的物品占两种容量至少为t和a。
设dp[i][j][k]为氧气量为j，氮气量为k时的最小重量
dp[i][j][k]=min{ dp [ i-1 ] [ j-t[i] ] [ k-a[i] ] + w[i] }
显然第一维可以在用循环覆盖省略掉
一开始我这样是这样写的
for (i=;i<=m;i++)
{
for (j=ti;j>=;j--)
{
for (k=ai;k>=;k--)
{
if (dp[j+t[i]][k+a[i]]>dp[j][k]+w[i])
{
dp[j+t[i]][k+a[i]]=dp[j][k]+w[i];
if (j+t[i]>=ti && k+a[i]>=ai) ans=min(ans,dp[j+t[i]][k+a[i]]);
}
}
}
}
然后就WA了，一开始怎么也找不到错误，后来发现是循环边界有问题，假如数据
显然答案是三个全部都用上，
当扫描到第三个物品时，j必须是2，才能假如该物品，但是代码中j不可能取到2，这里发生了错误。
更好的办法就是当j+t[i]>ti时一律将j+t[i]视为ti，k+a[i]视为ai。
for (i=;i<=m;i++)
{
for (j=ti;j>=;j--)
{
for (k=ai;k>=;k--)
{
x=j+t[i];if (x>ti) x=ti;
y=k+a[i];if (y>ai) y=ai;
if (dp[x][y]>dp[j][k]+w[i])
{
dp[x][y]=dp[j][k]+w[i];
}
}
}
}
完整代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 1005
#define MAXM 40005
#define INF 0x3fffffff
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag; int ti,ai,t[],a[],w[],dp[][]; int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&ti,&ai);
scanf("%d",&m);
for (i=;i<=m;i++)
{
scanf("%d%d%d",&t[i],&a[i],&w[i]);
} memset(dp,0x2f,sizeof(dp));
dp[][]=; ans=INF; for (i=;i<=m;i++)
{
for (j=ti;j>=;j--)
{
for (k=ai;k>=;k--)
{
x=j+t[i];
y=k+a[i];
if (x>ti) x=ti;
if (y>ai) y=ai;
if (dp[x][y]>dp[j][k]+w[i])
{
dp[x][y]=dp[j][k]+w[i];
}
}
}
}
printf("%d\n",dp[ti][ai]);
}
return ;
}