一. 01背包 01背包问题关键在于某个物品取还是不取，状态可以从上一个占用空间转移而来。 for(int i = 1; i <= n; i++) { for(int j = m; j >= c[i]; j--) { dp[j] = max(dp[j], dp[j - c[i]] + w[i]); } } 二. 完全背包 完全背包问题就…

[题目链接] 金明的预算方案 题目大意 有 $n$ 块钱，$m$ 个物品，有些物品是主件，有些物品是附件，主件和附件的关系是：一个主件最多两个附件，选附件必须选主件。每个物品有一个权值 $w$ ，有一个花费 $v$ 物品的贡献为 $w * v$，求最大贡献。 输入格式 第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 …