这题与普通$01$背包的不同点在于$至少$,从这里我们就能发现,$j-v1$和$k-v2$可能$<0$,也就是说所需的氧气和氢气大于至少值。那是这种情况要怎么解决呢?
既然氧气和氢气已经大于至少值,那么就不再需要从第$i-1$物品中再去挑选其他种方案了,用第i个物品已经足够,所以我们就可以用$f[0][0]$也就是$0$来判断是否更新。
#include<bits/stdc++.h>
using namespace std;
const int N = 90,M = 30;
int f[M][N];
int n,m,m_1;
int main()
{
cin>>m>>m_1;
cin>>n;
memset(f,0x3f,sizeof f);
f[0][0]=0;//氧气含量至少为0,氢气含量至少为0的方案的最小质量即为0
for(int i=1;i<=n;i++)
{
int v,v_1,w;
cin>>v>>v_1>>w;
for(int j=m;j>=0;j--)
for(int k=m_1;k>=0;k--)
f[j][k]=min(f[j][k],f[max(0,j-v)][max(0,k-v_1)]+w);
}
cout<<f[m][m_1];
}