https://oj.turingedu.cn/class/370/lesson/14/problem/10 '''cpp #include #include using namespace std; int n, m, dp[65][32005]; // dp[i][j] 表示前 i 个物品，价格不超过 j 的前提下，得到的最大总和
vector fj[65]; struct Node { int v, p, q; } a[65]; int main() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> a[i].v >> a[i].p >> a[i].q; if (a[i].q) { fj[a[i].q].push_back(i); } } for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { if (a[i].q) { dp[i][j] = dp[i - 1][j]; continue; } //不选 dp[i][j] = dp[i - 1][j]; //选主件 if (j - a[i].v >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].v] + a[i].v * a[i].p); if (fj[i].size() == 0) continue; //选主件和第一个附件 int u = fj[i][0]; if (j - a[i].v - a[u].v >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].v - a[u].v] + a[i].v * a[i].p + a[u].v * a[u].p); if (fj[i].size() == 1) continue; //选主件第二个附件 int h = fj[i][1]; if (j - a[i].v - a[h].v >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].v - a[h].v] + a[i].v * a[i].p + a[h].v * a[h].p); //主件和两个附件都选 //想想怎么写？ if (j - a[i].v - a[u].v - a[h].v >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].v - a[u].v - a[h].v] + a[i].v * a[i].p + a[u].v * a[u].p + a[h].v * a[h].p); } } cout << dp[n][m] << endl; return 0; } '''