备战蓝桥杯 Day9(背包dp)

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;//拦截非法的curV
	mx = 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                    不放0
			else 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;
}