背包dp
前言 :由于普通的背包板子太板了,所以不多赘述,直接讲有价值的
1.多重背包的二进制优化
把一个物品的数量二进制拆分,例如有10个价值a的物品,我们把它拆成1+2+4+3个,这样保证可以用这4个物品凑出想要的解 代码很妙
int k=1,c=物品数量,v=物品价值,cnt,a[];
while(k<=c){
a[++cnt]=v*k;
c-=k;
k*=2;
}
if(c!=0){
a[++cnt]=c*v;
}
2.01背包和完全背包的滚动数组
//01背包
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
//完全背包
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
发现在枚举j的时候顺序变了,为什么呢
01背包 dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-w[i]}+c[i])
所以滚动时,dp_{j}还没有被当前的i更新,所以dp_{j}表示上一层的dp_j
而完全背包 dp_{i,j}=max(dp_{i-1,j},dp_{i,j-w[i]}+c[i])
dp_j需要已经更新过的dp_j所以正着来
3.一道很有启发的题目
有价值1,2,3,4,5,6,7,8的物品个a_i件,最大能凑成的小于m的数(1\leq m \leq 1e18)
其实没什么思路,讲解后看了题解才搞懂
我们令d=gcd(1,2,3,4,5,6,7,8)=840
第一步:我们只用其中一种价值的物品去凑d
若最后的答案为ans ans=k\times d+c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8
c为凑完d后每种物品剩下的价值
如果c_i要大于d的话,我们可以在c_i提取一个d出来,所以最后其中任意一个的c_i是小于d的
你会发现,c_i的大小决定了前面可以凑出多少个d,所以这就是一个背包问题,c_i的和为背包容量,我们需要合理分配c_i的大小来保证能前面能选取更多的d
应为每个c都小于d,多以8个c会一定小于8\times d,这就是背包容量的最大值 dp_{i,j}表示前i个物品,c_i的和刚好为j时(即把d凑完后剩下的和),能组成多少个d,也就是式子里面的k
最后枚举c的和,然后计算答案
4.特殊数据的01背包
1.m\leq 1e9 \quad n\leq 100 \quad c\leq1000
把状态反过来,dp_{i,j}表示前i个物品获得价值为j时的最小重量
2.m\leq 2e5 \quad n\leq 2e5 \quad w\leq100
发现重量很小,所以每两个重量的差也会很小,所以当m比较大时,我们可以按照性价比排序选择,若当前剩余的m很大了,也就是说无论如何m短时间内都不会被选满,所以对背包影响可以忽略
但是当m很小的时候,我们每个物品就显得很重要了,这时我们用背包dp
5.bitset优化背包
bitset就是一个自定义长度,空间小,速度快的01序列 可以像二进制一样进行左移、右移、与、或、非、异或等操作
例如状态转移方程dp_{i,j}|=dp_{i-1,j-w}
此时我们就可以把dp_i这一整行定义为一个bitset,让他去或上dp_j这一行的bitset左移w位的bitset 左移w位,就相当于这个bitset的每一位都向前挪了t步,就相当于每一位下标减小了t
标签:背包,int,leq,DP,物品,dp,bitset From: https://www.cnblogs.com/laozhuma/p/17071465.html