#include <cstring>
#include <iostream>
using namespace std;
// 体积至多j, f[i] = 0, v >= 0
// 体积恰好j, f[0] = 0, f[i] = INF, v >= 0
// 体积至少j, f[0] = 0, f[i] = INF
// // 体积至少j
// const int N = 1000, V1 = 21, V2 = 79;
// int f[V1 + 1][V2 + 1]; // v1[N], v2[N], w[N];
// int knapsack(int v1[], int v2[], int w[], int n, int m1, int m2) {
// memset(f, 0x3f, sizeof f);
// f[0][0] = 0;
// for (int k = 0; k < n; k++) {
// for (int i = m1; i >= 0; i--) {
// for (int j = m2; j >= 0; j--) {
// int& x = f[max(0, i - v1[k])][max(0, j - v2[k])];
// // if (x != 0x3f3f3f3f) {
// // f[i][j] = min(f[i][j], x + w[k]);
// // }
// f[i][j] = min(f[i][j], x + w[k]);
// }
// }
// }
// return f[m1][m2];
// }
// 体积恰好j, bounded by m1 and m2
const int N = 1000, V1 = 21, V2 = 79;
int f[V1 + 1][V2 + 1]; // v1[K], v2[K], w[K];
int knapsack(int v1[], int v2[], int w[], int n, int m1, int m2) {
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int k = 0; k < n; k++) {
for (int i = m1; i >= 0; i--) {
for (int j = m2; j >= 0; j--) {
// if (f[i][j] != 0x3f3f3f3f) { // optional
int& x = f[min(i + v1[k], m1)][min(j + v2[k], m2)];
x = min(x, f[i][j] + w[k]);
// }
}
}
}
return f[m1][m2];
}
int main()
{
int n, m1, m2;
cin >> m1 >> m2 >> n;
int v1[N], v2[N], w[N];
for (int i = 0; i < n; i++) {
cin >> v1[i] >> v2[i] >> w[i];
}
cout << knapsack(v1, v2, w, n, m1, m2);
return 0;
}
想问一下为什么体积至少为j何体积恰好为j,f在转移的时候分别为int& x = f[max(0, i - v1[k])][max(0, j - v2[k])]和int& x = f[min(i + v1[k], m1)][min(j + v2[k], m2)];呢,里面的max和min为什么一定要加?
在至少为j的问题里,如果
for(int i=m1;i>=v1;i–){
for(int j=m2;j>=v2;j–){
f[i][j]=min(f[i][j],f[i-v1][j-v2]+w);
}
}
这样和加上max(0, i - v1[k])我感觉是一样的意思,为什么这个就不可以呀