关于多重背包问题(入门) 笔记

Lee Wen

2024-08-13 18:17:13

发布于：广东

46阅读

0回复

0点赞

多重背包问题

问题概览

难度：普及题目：洛谷P1776宝物筛选、ACGO A20907

本文以宝物筛选作为多重背包的讲解，我们将题意简化为下面的描述：

有一个背包容量为 $W$ ，还有 $n$ 种商品

它们的重量分别为 $w_1,w_2...w_n$ ，价值为 $v_1,v_2...v_n$ ，个数为 $m_1,m_2...m_n$

求在不超过背包的容量 $W$ 下所能获得的最大价值

从"01"到"多重"

多重背包不同于完全背包和01背包的，它对于任一物品 $i$ 只能够拿限定的 $m_i$ 件

在01背包的讲解中我们说01背包是背包问题的基础，而多重背包就可以转换为01背包

看到这个题目的时候我们可以很快想出一个方法，设 $k_i$ 为第 $i$ 件物品拿的数量，通过 $for$ 循环把多重问题转换为许多01背包问题

就是对于第 $i$ 件物品，可用资金为 $j$ ，拿取数量为 $k$ 时有拿或不拿两种状态 代码如下

	for(int i=1;i<=n;i++){
		for(int j=W;j>=0;j--){//所能用资金,有购买限制所以逆推 
			for(int k=0;k<=a[i].m;k++){//所能买的数量 
				if(a[i].v*k>j){
					break;//如果购买的价格大于可用资金结束当前遍历 
				}
				else DP[j]=maxn(DP[j],DP[j-a[i].v*k]+a[i].w*k);
			}
		}
  }

这样是可以通过低数据的情况，因为时间是 $O(W\Sigma\ m_i)$ ，但根据数据最大运算量为 $4\times10^9$ ，对于大数据必TLE

多重背包的时间优化(二进制优化)

为了AC这题，我们必须进行优化，在上面的算法当中我们把每一个物品都拆成了 $\Sigma\ m_i$ 件物品，这样运算量肯定很大

那我们是否可以通过减少拆分来使运算量变少呢？ $Absolutely\ YES\ !$

但如何定义拆分的量呢？我们知道定理任何整数都能分解成2的幂之和

因此可以将 $m_i$ 拆分为多个 $2^k$ 相加，避免了出现数据不一致的情况

例如给出一件物品 $i,w_i=1,v_i=1,m_i=600$ ，按照新算法分解为下面的形式

编号 $i$	$w_i$ 重量	$v_i$ 价值	选或不选
$1$	$1$	$1$	待定
$2$	$2$	$2$	待定
$3$	$4$	$4$	待定
$4$	$8$	$8$	待定
$5$	$16$	$16$	待定
$6$	$32$	$32$	待定
$7$	$64$	$64$	待定
$8$	$128$	$128$	待定
$9$	$256$	$256$	待定
$10$	$89$	$89$	待定

可以很直观感受到，如果按照先前的算法我们是要600次计算，而现在只需要10次，时间优化到了 $O(W\Sigma\log m_i)$

这样的方法叫"二进制优化"，毕竟任一数都可转换为二进制形式而且分解2的幂相加这一步很像二进制位的拆分

代码如下，~~写法应该肥肠容易理解吧~~

#include<bits/stdc++.h>
using namespace std;
int n,W;//n个种数,W载重 
struct Node{int v,w,m;}a[500005];//v价值w重量m可买数量,注意数据范围
int DP[600005];//当载重为j下所能获得的最大价值 
int main(){
	cin>>n>>W;
	int pos=0;//转化后的长度 
	for(int i=1;i<=n;i++){
		int v1,w1,m1,k=1;//k代表2的幂,即一次拆分出的量 
		cin>>v1>>w1>>m1;
		while(k<=m1){
			pos++;
			a[pos].v=v1*k;
			a[pos].w=w1*k;
			m1-=k;
			k*=2;
		} 
		if(m1){//如果m1中还有没拆分的，剩下的直接为一组 
			pos++;
			a[pos].v=v1*m1;
			a[pos].w=w1*m1; 
		}
	}
	for(int i=1;i<=pos;i++){//01背包
		for(int j=W;j>=a[i].w;j--){
			DP[j]=max(DP[j],DP[j-a[i].w]+a[i].v);
		} 
	}
	cout<<DP[W];
	return 0;
}