01背包問題

1267：【例9.11】01背包問題

【題目描述】

一個旅行者有一個最多能裝?M�?公斤的背包，現在有?n�?件物品，它們的重量分別是W1，W2，...,Wn�1，�2，...,��,它們的價值分別為C1,C2,...,Cn�1,�2,...,��，求旅行者能獲得最大總價值。

【輸入】

第一行：兩個整數，M�(背包容量，M<=200�<=200)和N�(物品數量，N<=30�<=30)；

第2..N+12..�+1行：每行二個整數Wi，Ci��，��，表示每個物品的重量和價值。

【輸出】

僅一行，一個數，表示最大總價值。

【輸入樣例】

10 4
2 1
3 3
4 5
7 9

【輸出樣例】

12

方法一：搜索（時間復雜度高--O（2^n））?

#include<iostream>
using namespace std;
const int N = 30;
int m,n,v[N], w[N];
int mx;
bool vis[N];//標記
//搜索狀態curV當前已選物品的總價值，curW當前已選物品的總重量
void dfs(int curV, int curW,int dep) {if (curW > m) return;//攔截非法的curVmx = max(mx, curV);//5.通用終止條件if (dep == n + 1)  return;//一共n件物品，n件物品已經搜完了，結束//找出搜索所有方案里面的最大價值//1.枚舉方案for (int i = 1; i <= n; i++) {//2.判斷標記-防止重復搜索if (!vis[i]) {//3.標記+搜索vis[i] = 1;dfs(curV + v[i], curW + w[i], dep + 1);//4.回溯vis[i] = 0;}}
}
int main() {cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}dfs(0, 0, 1);//初始狀態cout << mx << endl;return 0;
}

方法二dp

#include<iostream>
using namespace std;
const int N = 30, M = 2e2 + 10;
int m,n,v[N], w[N];
int dp[N][M];
/*
01背包
特點：n件物品，每件物品只有一件，要么選（1），要么不選（0）
樸素版本
狀態 dp[i][j] 前i件物品在背包容量不超過j的前提下構成的最大價值
狀態轉移方程 if(j<w[i]) dp[i][j]=dp[i-1][j];//放不下，不放
else if(j>=w[i]) dp[i][j]=max(dp[i-1][j-w[i]]+v[i]放,dp[i-1][j]不放)//可以放
滾動數組優化
dp[]
*/
int main() {cin >> m >> n;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];//時間復雜度O（n^2）for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j < w[i]) dp[i][j] = dp[i - 1][j];//放不下，不放//                                        放1                    不放0else if (j >= w[i]) dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);//可以放}}cout << dp[n][m] << endl;return 0;
}