一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
0搬砖 - 蓝桥云课 (lanqiao.cn)
二、解题报告
1、思路分析
将物品按照w[i] + v[i]升序排序然后跑01背包就是答案
下面证明：（不要问怎么想到的，做题多了就能想到，和谷歌那道能量石一样的套路）
对于物品i, j, 前面已经有了W
现：w[i] + v[i] <= w[j] + v[j]
且j 能排在前面 ，我们要推出 i 是否也能在前面
因为j在前面所以，v[j] >= W v[i] >= W + w[j]
结合[i] + v[i] <= w[j] + v[j]可推出：v[j] - w[i] >= v[i] - w[j] >= W
进而推出：v[j] >= W + w[i]
故i在前面时，v的价值大于前面的重量和，得证
那么对于任何一个最优解，我们按照w[] + v[]升序排序，不影响最优解的合法性，仍然得到最优解
换句话说，我们在原问题的集合中找到了一个小集合：w[] + v[]升序
且小集合中存在最优解
那么我们在这个小集合中跑01背包就能得到最优解
所以排序后跑01背包就行
注意倒序枚举时，容量初始为w[] + v[]
因为v[] >= m - w[] => m <= v[] + w[]
2、复杂度
时间复杂度： O(nlogn + Σ(v[i] + w[i]))空间复杂度：O(n)
3、代码详解
#include <bits/stdc++.h>const int N = 1010;int n, tot, m, f[200010];struct node {int w, v;bool operator < (const node& x) const {return v + w <= x.v + x.w;}
} nodes[N];int main () {std::cin >> n;for (int i = 0; i < n; i ++ ) std::cin >> nodes[i].w >> nodes[i].v, m += nodes[i].w;std::sort(nodes, nodes + n);for (int i = 0; i < n; i ++ )for (int j = std::min(m, nodes[i].w + nodes[i].v); j >= nodes[i].w; j -- )f[j] = std::max(f[j], f[j - nodes[i].w] + nodes[i].v);std::cout << *std::max_element(f, f + m + 1);return 0;
}