又是一道经典的背包问题，在洛谷上的链接：https://www.luogu.org/problemnew/show/P1064
和01背包不同的是，物品之间存在依赖关系，要想购买附件就必须购买主件，所以就可以这样想，从｛主件，主件+附件1，主件+附件2，主件+附件1+附件2｝中选择一个物品放入背包，然后使得总价值最大。这样只需要处理主件，处理每个主件时的状态转移方程修改一下就可以了，详见代码。同样的将其类比成01背包后，也可以将空间复杂度降到O(n)。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int maxn = 3205, maxm = 65; 7 8 int v[maxm][3], p[maxm][3], dp[maxn]; 9 10 int main() { 11 int n, m; 12 scanf("%d%d", &n, &m); 13 n /= 10; 14 for (int i = 1; i <= m; ++i) { 15 int a, b, c; 16 scanf("%d%d%d", &a, &b, &c); 17 a /= 10; 18 if (!c) v[i][0] = a, p[i][0] = b * v[i][0]; 19 else { 20 if (v[c][1]) v[c][2] = a, p[c][2] = b * v[c][2]; 21 else v[c][1] = a, p[c][1] = b * v[c][1]; 22 } 23 } 24 for (int i = 1; i <= m; ++i) if (v[i][0]) 25 for (int j = n; j >= v[i][0]; --j) { 26 dp[j] = max(dp[j], dp[j - v[i][0]] + p[i][0]); 27 if (j >= v[i][0] + v[i][1]) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][1]] + p[i][0] + p[i][1]); 28 if (j >= v[i][0] + v[i][2]) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][2]] + p[i][0] + p[i][2]); 29 if (j >= v[i][0] + v[i][1] + v[i][2]) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][1] - v[i][2]] + p[i][0] + p[i][1] + p[i][2]); 30 } 31 printf("%d", dp[n] * 10); 32 return 0; 33 }