算法
$O(n^2)$
$f(i,j)$表示获得v1至少是i并且获得v2至少是j的所有方案中的最小值。
那么状态转移方程为:$f(i,j) = \min (f(i,j),f(i-v1,j-v2)+w)$
但是有个很重要的不一样的地方:
这里解释下,如果当前i-1个数获得$f(0,0)$时候,那么第i个数选择获得$f(a,b)$= $\min f(0,0)$+w。
但是由于是至少,那么$f(a,b)$表示两个维度分别至少a,b的最小值
那么$f(c,d) ,(c<=a,d<=b)$两个维度至少是c,d的最小值是不是也可以是$f(a,b)$
但是$f(c,d)$得从$f(y,z) ,(y=c-v1<0,z=d-v2<0)$转移过来,但是这是不行的,所以必须得从$f(0,0)+w$来转移
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 22,M=80;
int n,m,k;//构成至少是n,m
int f[N][M];//f(i,j)表示v1至少是i,v2至少是j的所有方案中的最小值
int main()
{ cin>>n>>m>>k;
memset(f,0x3f,sizeof f);//至少是其他的状态现在都不合法,因为未知,由于求最小值,故去0x3f
f[0][0]=0;//至少是0,0的所有方案中,所有都不选择会获得最小值0
while(k--)
{
int a,b,w;
cin>>a>>b>>w;
for(int j=n;j>=0;j--)
{
for(int k=m;k>=0;k--)
{
f[j][k]=min(f[j][k],f[max(0,j-a)][max(0,k-b)]+w);
//这里解释下,当前i-1个数获得f[0][0]时候,那么第i个数选择获得f[a][b]=min f[0][0]+w。
//但是由于是至少,那么f(a,b)表示两个维度分别至少a,b的最小值
//那么f(c,d) (c<=a,d<=b)两个维度至少是c,d的最小值是不是也可以是f(a,b)
//但是f(c,d)得从f(y,z) (y<0,z<0)转移过来,但是这是不行的,所以可借用f(0,0)+w来转移
}
}
}
cout<<f[n][m];
return 0;
}