关于分数膨胀的问题，如何解决？(语言-c++)

题目描述
我们把USACO竞赛的试题分为若干类，每类都有2道题目。同一类题目分值相同，耗时也相同。你的任务是编写一个程序决定选择那些题目，使得考生在给定的时间内能得到尽可能多的分数。
输入

  • 第一行：包括两个整数M,N。M(1 ≤ M ≤ 10,000)代表竞赛的时间(min)，N（1 ≤ N ≤14）代表问题种类的数目
  • 第2..N+1行：包括两个整数--每类题目的分值(1 ≤ 分值 ≤ 10000)和耗时(1 ≤耗时≤ 10000)

输出
最大可能得到的分数

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;
int a[1009],v,n,b[1009],ans=INT_MIN;
void dfs(int dep,int r,int s)
{
    if(dep>n)
    {
        ans=max(ans,s);
    return ;
    }                                                                       
    dfs(dep+1,r,s);
    if(r>=a[dep])
    dfs(dep+1,r-a[dep],s+b[dep]);
}
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    dfs(1,v,0);
    cout<<ans<<endl;
    return 0;
}

//有设么也问题

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
在您提供的代码中，存在分数膨胀的问题，即同样的问题可能会被多次计算，从而导致得分偏高。这是因为在搜索过程中，每个问题只被考虑了一次，而实际上同一个问题可能会被选择多次，从而使得分数膨胀。

为了解决这个问题，可以采用记忆化搜索（Memoization）的方法，即在搜索过程中记录已经计算过的状态，避免重复计算。具体来说，可以使用一个二维数组 f[i][j] 表示在前 i 类问题中，用时不超过 j 分钟所能得到的最大分数。在搜索过程中，如果当前状态已经计算过，则直接返回已有的结果，否则进行搜索，并记录结果。

下面是使用记忆化搜索的 C++ 代码示例：

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;

int a[15], b[15];
int f[15][10001];

int dfs(int dep, int r) {
    if (dep == 0 || r <= 0) {
        return 0;
    }
    if (f[dep][r] != -1) {
        return f[dep][r];
    }
    int ans = dfs(dep - 1, r);
    if (r >= a[dep]) {
        ans = max(ans, dfs(dep, r - a[dep]) + b[dep]);
    }
    f[dep][r] = ans;
    return ans;
}

int main() {
    int v, n;
    cin >> v >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    memset(f, -1, sizeof(f));
    cout << dfs(n, v) << endl;
    return 0;
}

在上面的代码中，使用 f[i][j] 记录状态，初始化为 -1，表示尚未计算过。在搜索时，如果状态 f[i][j] 已经计算过，则直接返回结果，否则继续搜索，并记录结果。通过采用记忆化搜索的方法，可以避免分数膨胀的问题，得到正确的结果。

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢