题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#include <iostream> #include <vector> using namespace std; /*** 买附件,必须买主件 主件有0,1,2个附件。 每件的价格是10n,预算为N;每个物品的重要度[1, 5] 满意度: 价格与重要度的乘积的综合。 */ int main() { int N, m; cin >> N >> m; vector<int> v(m + 1); vector<int> p(m + 1); vector<int> q(m + 1); vector<bool> flag(m + 1, false); // 记录那些主件有附件 for (int i = 1; i <= m; i++) { cin >> v[i] >> p[i] >> q[i]; if (q[i] != 0) { flag[q[i]] = true; } } vector<int> f(N + 1, -0x7f7f7f7f); f[0] = 0; for (int i = 1; i <= m; i++) { // 附件不单独处理 if (q[i] != 0) continue; // 对主件的子背包进行处理 if (flag[i]) { int i_cnt = 0; int i_v = 0; vector<int> i_sub; for (int k = 1; k <= m; k++) { if (q[k] == i) { i_sub.push_back(k); i_cnt++; i_v += v[k]; } } i_v = min(N - v[i], i_v); vector<int> f_sub(i_v + 1, -0x7f7f7f); // f_sub的个数是值域 f_sub[0] = 0; for (int j = 0; j < i_cnt; j++) { for (int k = i_v; k >= v[i_sub[j]]; k--) { f_sub[k] = max(f_sub[k], f_sub[k - v[i_sub[j]]] + v[i_sub[j]] * p[i_sub[j]]); // if(f_sub[k] > 0){ // printf("i_v:%d, j:%d, k:%d, f_sub[k-v[j]]:%d, add:%d, f[new]:%d\n", // i_v, i_sub[j], k, f_sub[k - v[i_sub[j]]], v[i_sub[j]] * p[i_sub[j]], f_sub[k]); // } } } // 主件进行背包,并将主件的副件的子背包嵌入 for (int j = N; j >= v[i]; j--) { // 处理主件 f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]); // if (f[j] > 0) { // printf("i:%d, j:%d, f[j-v[i]]:%d, add:%d, f[j]:%d\n", i, j, f[j - v[i]], v[i] * p[i], f[j]); // } // 将子背包与父件合并,并同步至父背包 for (int k = 0; k <= i_v; k++) { if (f_sub[k] > 0 && j - v[i] - k >= 0) { f[j] = max(f[j], f[j - v[i] - k] + f_sub[k] + v[i] * p[i]); // if(f[j] > 0){ // printf("merge, j:%d, k:%d, f[j-v[i]-k]:%d, add:%d, f[j]:%d\n", j, k, f[j - v[i] - k], // f_sub[k] + v[i] * p[i], f[j]); // } } } } } // 对没有子件的背包进行处理 else{ for (int j = N; j >= v[i]; j--) { f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]); // if (f[j] > 0) { // printf("nosub_i:%d, j:%d, f[j-v[i]]:%d, add:%d, f[j]:%d\n", i, j, f[j - v[i]], v[i] * p[i], f[j]); // } } } } int ans = 0; for (int i = 1; i <= N; i++) { if (f[i] > ans) ans = f[i]; } cout << ans << endl; return 0; } // 64 位输出请用 printf("%lld")