一、題目

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;
}