WA了第一第二个点,求大佬解惑
查看原帖
WA了第一第二个点,求大佬解惑
760035
wangleisysu楼主2022/8/22 13:41

其实我连测试用例都不是很理解,测试用例中第一组不是应该最大价值为15嘛?为啥是10?

我写了这个程序得分是98,第一第二个测试点没过,很疑惑。求助大佬们 ORZ

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
    int group, m, n, maxgroup = 0, maxValue = 0;
    cin >> m >> n;
    vector<int> dp(m + 1);
    vector<int> weights(n + 1), values(n + 1);
    vector<vector<int>> Groups(1010, vector<int>(1));
    for (int i = 1; i <= n; ++i) {
        cin >> weights[i] >> values[i] >> group;
        Groups[group].push_back(i);
        maxgroup = max(maxgroup, group);
    }
    for (int g = 0; g <= maxgroup; ++g) {
        for (int i = 1; i < Groups[g].size(); ++i) {
            for (int j = m; j >= weights[Groups[g][i]]; --j) {
                dp[j] = max(dp[j], dp[j - weights[Groups[g][i]]] + values[Groups[g][i]]);
            }
        }
        maxValue = max(maxValue, dp[m]);
    }
    
    cout << maxValue << endl;
    return 0;
}
2022/8/22 13:41
加载中...