From a8f8345aee0f4bc7a4ce9e4bb617aba3165756ae Mon Sep 17 00:00:00 2001 From: ZHB <45039623+zhb2000@users.noreply.github.com> Date: Sun, 10 Jan 2021 00:13:32 +0800 Subject: [PATCH] =?utf8?q?=E4=BF=AE=E6=94=B9=E5=AE=8C=E5=85=A8=E8=83=8C?= =?utf8?q?=E5=8C=85=E7=9A=84=E4=BE=8B=E9=A2=98=E4=BB=A3=E7=A0=81?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/dp/knapsack.md | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-) diff --git a/docs/dp/knapsack.md b/docs/dp/knapsack.md index afbac202..8511ab94 100644 --- a/docs/dp/knapsack.md +++ b/docs/dp/knapsack.md @@ -104,16 +104,21 @@ $$ ??? 例题代码 ```cpp #include - const int maxn = 1e5 + 10; - int n, W, w[maxn], v[maxn], f[maxn]; - int main() { - std::cin >> W >> n; - for (int i = 1; i <= n; i++) std::cin >> w[i] >> v[i]; - for (int i = 1; i <= n; i++) - for (int l = w[i]; l <= W; l++) - if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i]; - std::cout << f[W]; - return 0; + const int maxn = 1e4 + 5; + const int maxW = 1e7 + 5; + int n, W, w[maxn], v[maxn]; + long long f[maxW]; + int main() + { + std::cin >> W >> n; + for (int i = 1; i <= n; i++) + std::cin >> w[i] >> v[i]; + for (int i = 1; i <= n; i++) + for (int l = w[i]; l <= W; l++) + if (f[l - w[i]] + v[i] > f[l]) + f[l] = f[l - w[i]] + v[i]; + std::cout << f[W]; + return 0; } ``` -- 2.11.0