题解：P1782 旅行商的背包

~~写篇题解纪念一下本苣蒻不看题解标签做出来的第一道蓝题。~~

思路

题意已经十分明显了。这是一道混合背包问题。

我们可以把物品分成两类——第一类普通物品，第二类奇货。

第一类

多重背包的板子。

看一眼数据范围直接暴力肯定会超时。需要进行优化。

多重背包的优化有二进制拆分及单调队列两种方法。这里我选用了二进制拆分。

二进制拆分顾名思义就是把

k

个物品

i

拆分成

1

、

2

、

4

……个，最后可以变为01背包。具体讲解可以看看这个。

我的代码使用的是边 dp 边拆分的方法。也可以先拆分预处理数组再进行 dp 运算。

第二类

m

很小，可以直接暴力。

可以看作分组背包。每个奇货为一组。组内物品体积为

0

C

，价值使用题目所给公式计算。

一些细节

十年 oi 一场空，不开 long long 见祖宗。

注意奇货的体积要从

0

开始枚举。不难发现体积

x

为

0

时仍有价值为

c

。

Code

CPP

#include<bits/stdc++.h>
#define lg long long
using namespace std;
lg n,m,C,v[10010],w[10010],p[10010],a,b,c,d[10010],ans;
int main(){
	scanf("%lld%lld%lld",&n,&m,&C);
	for(lg i=1;i<=n;i++){
		scanf("%lld%lld%lld",&v[i],&w[i],&p[i]);
	}
	for(lg i=1;i<=n;i++){
		for(lg k=1;k<=p[i];k<<=1){
			for(lg j=C;j>=v[i]*k;j--){
				d[j]=max(d[j],d[j-v[i]*k]+w[i]*k);
			}
			p[i]-=k;
		}
		if(p[i]){
			for(lg j=C;j>=v[i]*p[i];j--){
				d[j]=max(d[j],d[j-v[i]*p[i]]+w[i]*p[i]);
			}
		}
	}//多重背包 
	for(lg i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		for(lg j=C;j>=0;j--){
			for(lg k=0;k<=j;k++){
				d[j]=max(d[j],d[j-k]+a*k*k+b*k+c);
			}
		}
	}//奇货 
	for(int i=0;i<=C;i++){
		ans=max(ans,d[i]);
	}
	printf("%lld",ans);
	return 0;
}

题解：P1782 旅行商的背包

文章操作

思路

第一类

第二类

一些细节

Code

相关推荐

评论

题解：P1782 旅行商的背包