文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

有 N 件物品和一個容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 vi，價值是 wi。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。

輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。

輸出格式
輸出一個整數，表示最大價值。

數據范圍
0<N,V≤1000
0<vi,wi≤1000

輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例：
8

題目來源：https://www.acwing.com/problem/content/description/2/

2. 解題

• dp[v] 表示體積為 v 時裝的最大價值
• 時間復雜度 $O(NV)$，空間復雜度 $O(V)$

#include<bits/stdc++.h> using namespace std;int main() {int N, V, vi, wi, maxprice = 0;cin >> N >> V;vector<int> dp(V+1, -1);dp[0] = 0;// dp[v] 表示體積為 v 時裝的最大價值for(int i = 0; i < N; ++i){cin >> vi >> wi;for(int j = V-1; j >= 0; --j){ //逆向遍歷，新生成的狀態不會影響后序的遍歷if(dp[j] == -1 || j+vi > V)continue;dp[j+vi] = max(dp[j+vi], dp[j]+wi);maxprice = max(maxprice, dp[j+vi]);}}cout << maxprice << endl;return 0; }

69 ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的ACwing 2. 01背包问题（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。