这道题的难点在于价值可以多。
这道题我一开始用的是前面的状态推现在的状态
实现比较麻烦，因为价值可以多，所以就设最大价值
为题目给的最大价值乘以10
#include<cstdio>
#include<algorithm>
#include<cstring>
#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<cstdio>
#include<algorithm>
#include<cstring>
#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;
}