这道题的难点在于价值可以多。

这道题我一开始用的是前面的状态推现在的状态

实现比较麻烦，因为价值可以多，所以就设最大价值

为题目给的最大价值乘以10

#include
    
     #include
     
      #include
      
       #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 1123;const int MAXM = 112;int f[MAXN][MAXN], n, m1, m2;int a[MAXN], b[MAXN], w[MAXN];int main(){	scanf("%d%d%d", &m1, &m2, &n);	REP(i, 0, n) 		scanf("%d%d%d", &a[i], &b[i], &w[i]);			int ans = 1e9;	memset(f, 0x3f, sizeof(f));	f[0][0] = 0;		REP(i, 0, n)		for(int j = m1 * 10; j >= a[i]; j--)			for(int k = m2 * 10; k >= b[i]; k--)			{				f[j][k] = min(f[j][k], f[j-a[i]][k-b[i]] + w[i]);				if(j >= m1 && k >= m2) ans = min(ans, f[j][k]);			}	printf("%d\n", ans);		return 0;}
      
     
    

然后后来发现好像用当前更新后来的状态是更方便的

只需要在超过最大价值的时候取最大价值就好了。

#include
    
     #include
     
      #include
      
       #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 1123;const int MAXM = 112;int f[MAXN][MAXN], n, m1, m2;int a[MAXN], b[MAXN], w[MAXN];int main(){	scanf("%d%d%d", &m1, &m2, &n);	REP(i, 0, n) 		scanf("%d%d%d", &a[i], &b[i], &w[i]);			memset(f, 0x3f, sizeof(f));	f[0][0] = 0;	REP(i, 0, n)		for(int j = m1; j >= 0; j--)			for(int k = m2; k >= 0; k--)			{				int t1 = min(m1, j + a[i]), t2 = min(m2, k + b[i]);				f[t1][t2] = min(f[t1][t2], f[j][k] + w[i]);			}	printf("%d\n", f[m1][m2]);		return 0;}