备战蓝桥杯 Day11(滚动数组优化+完全背包)

01背包的滚动数组优化

【题目描述】

经典0—1背包问题,有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。

#include<iostream>
using namespace std;

const int N = 3500, M = 12800;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i件物品在背包容量不超过j的情况下的最大价值
//状态转移方程 if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	//01背包的滚动数组优化
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= w[i]; j--) //01背包滚动数组优化的时候，注意j要逆推
		{
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m] << endl;
	return 0;
}

 完全背包

1268：【例9.12】完全背包问题

【题目描述】

设有n�种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M�，今从n�种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M�，而价值的和为最大。

#include<iostream>
using namespace std;

const int N = 30, M = 200;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值
//状态转移方程
/*
dp[j]=max{
			dp[j-0*w[i]]+0*v[i],
            dp[j-1*w[i]]+1*v[i],
			dp[j-2*w[i]]+2*v[i],
			dp[j-3*w[i]]+3*v[i],
			...
			dp[j-m/w[i]*w[i]]+m/w[i]*v[i]
		 }
*/
int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

	//完全背包朴素版本
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 1; j--)
			for (int k = 1; k <= m / w[i]; k++)
			   if(j>=k*w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);

	cout <<"max=" << dp[m] << endl;
	return 0;
}

多重背包

【题目描述】

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

多重背包

特点：n种物品，每件物品有指定数量s[i]（真实数量上限：min(m/w[i],s[i])）

状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值

int main() { 
	cin  >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]>>s[i];

	//多重背包朴素版本
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 1; j--)
			for (int k = 1; k <= min(m / w[i], s[i]); k++)//针对第i种物品，得到选k件的最优解
				if (j >= k * w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);

	cout << dp[m] << endl;
	return 0;
}