记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,v,m;
int V[N], M[N], S[N];
int memo[N][110][110]; // 记忆化表
int dfs(int x, int prv, int prm) {
if (x > n) return 0; // 基本情况
// 检查结果是否已经计算过
if (memo[x][prv][prm] != -1) return memo[x][prv][prm];
int res = 0;
if (prv < V[x] || prm < M[x])
res = dfs(x + 1, prv, prm);
else if (prv >= V[x] && prm >= M[x])
res = max(dfs(x + 1, prv, prm), dfs(x + 1, prv - V[x], prm - M[x]) + S[x]);
// 将结果存储在记忆表中
memo[x][prv][prm] = res;
return res;
}
int main() {
memset(memo, -1, sizeof(memo)); // 使用-1初始化记忆表
scanf("%d%d%d", &n, &v, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &V[i], &M[i], &S[i]);
}
int res = dfs(1, v, m);
printf("%d", res);
return 0;
}
从下往上
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,v,m;
int V[N], M[N], S[N];
int f[N][110][110];
int main() {
scanf("%d%d%d", &n, &v, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &V[i], &M[i], &S[i]);
}
for(int i=n;i>=1;i--)
{
for(int j=0;j<=v;j++)
{
for(int k=0;k<=m;k++)
{
if(j<V[i]||k<M[i])
{
f[i][j][k]=f[i+1][j][k];
}
else{
f[i][j][k]=max(f[i+1][j][k],f[i+1][j-V[i]][k-M[i]]+S[i]);
}
}
}
}
printf("%d",f[1][v][m]);
return 0;
}
降维操作
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,v,m;
int V[N], M[N], S[N];
int f[110][110];
int main() {
scanf("%d%d%d", &n, &v, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &V[i], &M[i], &S[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=V[i];j--)
{
for(int k=m;k>=M[i];k--)
{
f[j][k]=max(f[j][k],f[j-V[i]][k-M[i]]+S[i]);
}
}
}
printf("%d",f[v][m]);
return 0;
}