其实我连测试用例都不是很理解,测试用例中第一组不是应该最大价值为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;
}