动态规划——多重背包问题

多重背包问题

4. 多重背包问题 I - AcWing题库

1269：【例9.13】庆功会

多重背包

5. 多重背包问题 II - AcWing题库

有 N N N种物品和一个容量为 V V V的背包。第 i i i种物品最多有 s i s_i si​件可用，每件的体积是 w i w_i wi​，价值是 v i v_i vi​。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

这里可以套用完全背包的分析思路。

借鉴完全背包问题的思路

  1. 状态定义

    令dp[i][j]表示前i种物品，每种选若干个，这些物品恰好放入一个容量为j的背包时的最大价值。假设j最多能放k个i物品。

  2. 转移方程

  • 当只有1种物品的时候，没得选，包能塞多少就装多少。

  • 当不止有1种物品时，假设前i-1种物品都已经选择好了最大价值的方案，第i种物品的数量和最大价值的关系：

当i物品不选时，dp[i][j]=dp[i-1][j]，

当选1件i物品时，dp[i][j]=dp[i-1][j-w[i]]+v[i]

当选2件i物品时，

dp[i][j]=dp[i-1][j-2*w[i]]+2*v[i]

⋯ \cdots ⋯
当选k件i物品时（k=s[i]），
dp[i][j]=dp[i-1][j-k*w[i]]+k*v[i]

当选k+1件物品时，该物品不能选了，所以就不选。

在众多的方案每次都选择最大价值的那个。

所以状态转移方程：

dp[i][j]=max{
    dp[i-1][j],
    dp[i-1][j-w[i]]+v[i],
    dp[i-1][j-2*w[i]]+2*v[i],
    ...
    dp[i-1][j-k*w[i]]+k*v[i]
}

多重背包无法和完全背包那样对转移方程做优化。

例如：

dp[i][j-w[i]]+v[i]=max{
    dp[i-1][j-w[i]]+v[i],
    dp[i-1][j-2*w[i]]+2*v[i],
    dp[i-1][j-3*w[i]]+3*v[i],
    ...
    dp[i-1][j-k*w[i]]+k*v[i],
    dp[i-1][j-(k+1)*w[i]]+(k+1)*v[i],
}

因为数量限制，多重背包的一种物品可能无法装满背包，所以dp[i-1][j-(k+1)*w[i]]+(k+1)*v[i]是非法状态，所以无法等价替换，也就无法对方程优化。

  1. 初始化&填表

dp[i][j]开始全为0即可。

dp[i][j]的更新方式是从上一行的左边选择状态更新，所以循环方式是i在外层枚举物品，之后第2层循环j表示不同大小的容量的背包，不做空间优化的话正向、反向枚举都可以。最后一层嵌套循环k，表示每个物品最多能选择的个数。即确定好包的容量和物品的数量后对不同数量的同种物品进行枚举。

所以代码实现：

for(int i=1;i<=N;i++)
    for(int j=0;j<=V;j++)//也可以for(int j=N;j>=0;j--)
        for(int k=0;k<=s[i];k++)//当k=0时，dp[i][j]=dp[i-1][j]
            if(j>=k*w[i])//if可以加在for循环的判断里
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);

时间复杂度 O ( N ∗ V ∗ Σ s i ) O(N*V*\Sigma s_i) O(N∗V∗Σsi​)，最坏情况 O ( n 3 ) O(n^3) O(n3)。

OJ4. 多重背包问题 I - AcWing题库和1269：【例9.13】庆功会参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<bits/stdc++.h>
using namespace std;

void ac1() {
	int n, V;
	cin >> n >> V;
	vector<vector<int> >dp(n+1, vector<int>(V + 1, 0));
	vector<int>v(n + 1, 0), w(v), s(v);
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i] >> s[i];
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= V; j++)
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k*w[i]);
	cout << dp[n][V];
}

int main() {
	ac1();
	return 0;
}

多重背包只需要在4. 多重背包问题 I - AcWing题库 的基础上交换物品数和质量、价值的输入顺序即可，即更改cin的顺序。

多重背包参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<bits/stdc++.h>
using namespace std;

void ac1() {
	int n, V;
	cin >> n >> V;
	vector<int>dp(V + 1, 0);
	vector<int>v(n + 1, 0), w(v), s(v);
	for (int i = 1; i <= n; i++)
		cin  >> s[i]>> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
		for (int j = V; j >= 0; j--)
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
				dp[j] = max(dp[j], dp[j - k * v[i]] + k*w[i]);
	cout << dp[V];
}

int main() {
	ac1();
	return 0;
}

5. 多重背包问题 II - AcWing题库因为数据量增大，需要用二进制优化。

空间优化

因为dp[i][j]的状态都是继承dp[i-1][j]，所以可以用空间优化：

设dp[j]为在容量不超过j的情况下，任选前i种物品，每种物品若干件，这些物品组成的最大价值。

转移方程：dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])。

循环方式：j需要从V到1进行枚举。因为dp[i]是一维，它的状态由dp[j-k*w[i]]转移而来，只有先确定之前的状态才能正常转移。而dp[i][j]的状态由dp[i-1][j]转移而来，所以顺序从V到1和从1到V都能得到相同的结果。

所以代码实现：

for(int i=1;i<=n;i++)
    for(int j=V;j>=1;j--)
        for(int k=0;k<=s[i];k++)
            if(j>=k*s[i])
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);

多重背包参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<bits/stdc++.h>
using namespace std;

void ac1() {
	int n, V;
	cin >> n >> V;
	vector<int>dp(V + 1, 0);
	vector<int>v(n + 1, 0), w(v), s(v);
	for (int i = 1; i <= n; i++)
		cin >> s[i] >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
		for (int j = V; j >= 0; j--)
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
				dp[j] = max(dp[j], dp[j - k * v[i]] + k*w[i]);
	cout << dp[V];
}

int main() {
	ac1();
	return 0;
}

4. 多重背包问题 I - AcWing题库也可以在多重背包的基础上更改cin的顺序即可。

二进制优化

二进制优化可以用于求最大价值的问题，求方案数不能用二进制优化，否则会多计算一些情况。

二进制优化的具体思路：

将第 i i i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1 , 2 , 4 , . . . , 2 k − 1 , n i − 2 k + 1 1,2,4,...,2^{k-1}, n_i-2^{k}+1 1,2,4,...,2k−1,ni​−2k+1，且 k k k是满足 n i − 2 k + 1 > 0 n_i-2^k+1>0 ni​−2k+1>0的最大整数。

这些系数已经可以组合出[1,n[i]]内的所有数字。例如，如果n[i]为13，就将这种物品分成系数分别为{1,2,4,6}的四件物品。

分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。

每种物品都按类似的方法去分，就将 i i i 种物品分成了约 Σ ( [ log ⁡ 2 n i ] + 1 ) \Sigma ([\log_2n_i]+1) Σ([log2​ni​]+1)种物品，将原问题转化为了时间复杂度为 O ( V ⋅ [ log ⁡ 2 n i ] ) O(V\cdot [\log_2n_i]) O(V⋅[log2​ni​])的01背包问题，是很大的改进。代价是额外申请了多余的空间。

数列 { 1 , 2 , 4 , . . . , 2 k − 1 , n i − 2 k + 1 } \{1,2,4,...,2^{k-1},n_i-2^{k}+1\} {1,2,4,...,2k−1,ni​−2k+1}一共有 k + 1 k+1 k+1项，

设前 k k k项的和为 S S S，根据等比数列前 n n n项和公式，

S = 1 − 2 k 1 − 2 = 2 k − 1 S=\frac{1-2^{k}}{1-2}=2^{k}-1 S=1−21−2k​=2k−1，于是 k = log ⁡ 2 ( S + 1 ) k=\log_2(S+1) k=log2​(S+1)。

已知 n i ≥ S n_i\geq S ni​≥S，所以第 i i i种物品分成了约 [ log ⁡ 2 n i ] + 1 [\log_2n_i]+1 [log2​ni​]+1种物品（不大于 log ⁡ 2 n i \log_2 n_i log2​ni​的最大整数，多出来的1种是分完后剩下的无法凑成2的指数幂的情况），

所有物品也就分成了约 Σ [ log ⁡ 2 n i ] + 1 \Sigma [\log_2n_i]+1 Σ[log2​ni​]+1种。

多余的空间也可以根据 [   log ⁡ 2 n i   ] + 1 [\ \log_2n_i\ ]+1 [ log2​ni​ ]+1进行计算。例如 n i ≤ 20 n_i\leq 20 ni​≤20，则每种物品最多能分成{1,2,4,8,5}这5个不同系数的物品，最多有 T T T种类似的物品，所以用到的空间最多为 5 T 5T 5T。

OJ5. 多重背包问题 II - AcWing题库 因为加大了数据量级，所以需要用到二进制优化：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<iostream>
#include<vector>
using namespace std;

void ac1(){
	int n,V;
	cin>>n>>V;
	vector<int>v(1,0),w(1,0);
	
	//二进制优化 
	for(int i=1;i<=n;i++){
		int tv,tw,s;//tv,template v
		cin>>tv>>tw>>s;
		int bas=1;
		while(s>=bas){
			v.push_back(tv*bas);
			w.push_back(tw*bas);
			s-=bas;
			bas*=2;
		}
		v.push_back(s*tv);
		w.push_back(s*tw);
	}
	vector<int>dp(V+1,0);
	for(int i=1;i<v.size();i++)
		for(int j=V;j>=v[i];j--)
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	cout<<dp[V];
}

int main() {
	ac1();
	return 0;
}

二进制优化也适用于完全背包。原理基本相同，可选数量默认为 [ V w i ] [\frac{V}{w_i}] [wi​V​]。

多重背包求方案数

为啥二进制优化为啥不能用于求多重背包的方案数。

例如第i种物品有9件，通过二进制优化得到系数为{1,2,4,2}的不同物品，假设其中一种状态的背包的选法要选系数为2的物品，所以这里有2种方案。如果是01背包的话这么想没问题，但完全背包的话是这里系数为2的物品全都出自同一种物品，所以它们只能算作1种方案。而且其他种数的物品也不保证会不会出现这种情况，所以二进制优化不能用于求多重背包的方案数。

[P1077 NOIP 2012 普及组] 摆花 - 洛谷

1959：【12NOIP普及组】摆花

这个题的大意是每种物品的费用和价值都是1但数量有限，问在能装满给定的背包容量的前提下（在某种限定条件下），有多少种方法。

所以这题是多重背包求方案数。

  1. 状态表示

dp[i][j]表示[1,i]中选，正好为j的情况下的方案数。所以最终的结果是dp[n][m]。

  1. 转移方程

根据最后一个物品的情况讨论。第i种物品有num[i]个，所以从不选到全选有num[i]+1个选择。

所以转移方程：

dp[i][j]=max{dp[i-1][j],dp[i-1][j-1],...,dp[i-1][j-k]},k<=j&&k<=a[i]
  1. 初始化&填表&最终答案

默认方案是dp[0][0]，将dp[0][0]=1即可。

按照多重背包的填表顺序即可。

最终答案是dp[n][m]。

  1. 空间优化

因为状态都是从上一层状态转移来，所以用一个数组即可。

但第2层枚举背包容量的循环要逆序，否则会将旧的状态覆盖，造成状态转移时的错误。

第3层循环不能从0开始，否则会重复计数。

参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<bits/stdc++.h>
using namespace std;

const int M = 1e6 + 7;

void ac1() {
	int n, m;
	cin >> n >> m;
	vector<int>num(n + 1, 0);
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	vector<vector<int> >dp(n + 1, vector<int>(m + 1, 0));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= m; j++)//二维状态这一层循环的顺序就无所谓
			for (int k = 0; k <= num[i] && k <= j; k++)
				dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % M;
	cout << dp[n][m];
}

void ac2() {
	int n, m;
	cin >> n >> m;
	vector<int>num(n + 1, 0);
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	vector<int>dp(m + 1, 0);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 0; j--)//空间优化后只有一维，循环只能逆序
			for (int k = 1; k <= num[i] && k <= j; k++)//k的初始值不能为0，否则会出现重复计数
				dp[j] = (dp[j] + dp[j - k]) % M;
	cout << dp[m];
}

int main() {
	//ac1();
	ac2();//空间优化
	return 0;
}

多重背包OJ汇总

  1. 模板题

4. 多重背包问题 I - AcWing题库

1269：【例9.13】庆功会

多重背包

  1. 二进制优化

5. 多重背包问题 II - AcWing题库

  1. 多重背包求方案数

[P1077 NOIP 2012 普及组] 摆花 - 洛谷

1959：【12NOIP普及组】摆花

# 动态规划 # 算法 # c++
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR 技术科普：光波导是什么，为什么警务要用它

avatar 乐奇 Rokid 开放社区
cover

LVGL嵌入式UI开发教程：AIUI Studio可视化编辑器实操指南

avatar 乐奇 Rokid 开放社区
cover

影目Air3被召回，智能眼镜迎来散热大考

avatar 乐奇 Rokid 开放社区