k622 - [棕]0-1背包問題
題目描述
題目描述了經典的 0-1 背包問題。給定 n 個物品，每個物品有重量 w 和價值 c，以及背包容量 k。目標是選擇一些物品放入背包，使得總重量不超過 k，且總價值最大。每個物品只能選擇一次（0 或 1）。
解題思路
此程式碼使用動態規劃的概念，但並未使用傳統的 dp 表格。它使用一個 map mp 來儲存所有可能的背包重量（key）及其對應的最大價值（value）。
程式碼的邏輯如下：
- 初始化
mp，將重量 0 的最大價值設為 0。 - 迭代每個物品。
- 對於
mp中的每個已知的重量和最大價值，考慮兩種情況：- 不選擇當前物品：將當前重量和最大價值複製到
nxtmap 中。 - 選擇當前物品：如果將當前物品放入背包後，總重量不超過 k，則在
nxtmap 中更新對應的重量和最大價值。
- 不選擇當前物品：將當前重量和最大價值複製到
- 將
nxtmap 賦值給mp，以便在下一次迭代中使用更新後的重量和最大價值。 - 迭代完成後，
mp中儲存了所有可能的背包重量及其對應的最大價值。找到mp中最大的價值，即為最終答案。
複雜度分析
- 時間複雜度: O(n * k) (因為 map 的迭代次數取決於 k 的大小，最壞情況下需要遍歷所有可能的重量組合)
- 空間複雜度: O(k) (map
mp最多儲存 k 個不同的重量)
程式碼
#include <bits/stdc++.h>
using namespace std;
long long a[25][2],n,k,ans;
map <long long,long long> mp;
map <long long,long long> :: iterator it;
int main(){
cin >> n >> k;
for(int j=0;j<2;++j)
for(int i=0;i<n;++i)
cin >> a[i][j];
mp[0]=0;
for(int i=0;i<n;++i){
map <long long,long long> nxt;
for(it=mp.begin();it!=mp.end();++it){
nxt[it->first] = max(it->second,nxt[it->first]);
if(it->first+a[i][0]<=k){
nxt[it->first+a[i][0]]=max(nxt[it->first+a[i][0]],it->second+a[i][1]);
}
}
mp=nxt;
}
for(it=mp.begin();it!=mp.end();++it){
ans=max(ans,it->second);
}
cout << ans;
}
//9640007