当前位置：首页 > article >正文

动态规划之背包问题

article 2025/2/21 23:24:28

动态规划是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

01背包问题

完全背包问题

多重背包问题

二维费用背包问题

（1）01背包问题

给定n个物体，和一个容量为c的背包，物品i的重量为wi，其价值为应该如何选择装入背包的物品使其获得的总价值最大。

可以用贪心算法，但是不一定能达到最优解，所以用动态规划解决

创建一个数组 dp[i][j] i为物品，j为容量，代表的值为价值

接下来要做的就是求状态转移方程

两种情况选择拿和不拿，假设w[i]为第i个的重量，c[i]为第i个的价值

推导过程如下

所以最后的状态转移方程为

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])

所以该题的解为

#include<iostream>
#include<algorithm>
using namespace std;
int dp[35][35];
int w[35], c[35];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];
	}
	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];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]]+ c[i]);
		}
	}
	cout << dp[n][m];
	return 0;

}

也可以进行优化，因为dp的值只和上一个数据相关，所以可以循环不断更新新数据

dp[j]=max(dp[j],dp[j-w[i]]+c[i])

所以优化后完全状态的01背包代码就为（j要从后往前推，不然上一次数据可能被吞掉）

#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j>=1; j--) {
			if (j > w[i])
				dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
		}
	}
	cout << dp[m];
	return 0;

}

（2）完全背包问题

直接上题

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

完全背包与01背包的区别就是完全背包的物品数量是无限的

先来个简单的方法：不断往背包中装入物品，直到背包装满

当前背包的容量j/w[i]

在01背包中加一个k循环，决定拿k个i物品，然后求价值的最大值

即for（k=0;k<i/w[i];k++) dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i])

#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j>=1; j--) {
			for (int k = 0; k < i / w[i]; k++)
				dp[j] = max(dp[j], dp[j - k * w[i]] + k * c[i]);
		}
	}
	cout << dp[m];
	return 0;

}

（但是这样做时间复杂度太高了，所以我们需要再优化一下）

优化后的状态转移方程为

dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i])

与01背包的区别就是从i开始而不是从i-1不需考虑上一层的状态

再将二维数组压缩成一维数组

dp[j]=max(dp[j],dp[j-w[i]]+c[i])

方程与01背包一样，但是应该从顺向推导，用到的是新数据

所以完全背包的终极写法为

#include<iostream>
#include<algorithm>
using namespace std;
int dp[205];
int w[35], c[35];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j<=m; j++) {
			if(j>=w[i])
				dp[j] = max(dp[j], dp[j -  w[i]] +  c[i]);
		}
	}
	cout << dp[m];
	return 0;

}

（3）多重背包问题

再来个小题

有n种物品和一个容量为v的背包，第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

与前两种背包的区别是每种有限件

用完全背包的思维，不断拿第i个物品个数小于等于n[i]，但是总重量小于背包容量

#include<iostream>
#include<algorithm>
using namespace std;
int dp[6100];
int w[510], v[510],s[510];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i]>>s[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j>=1; j--) {
			for (int k = 0; k <= s[i] && j >= k * v[i]; ++k) {
				dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
			}
		}
	}
	cout << dp[m];
	return 0;

}

依旧是熟悉的配方，我们来个优化（时间复杂度太高，当s很大时根本过不了）

多重背包的二进制优化（嘿嘿，不会）