题目描述
多重背包-二进制拆分
我发现啊,题解中都是用的都是LYD讲的可行性
简化版,所以发一个可以求最优解
的方法。
样例
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
8
4
算法1
(背包 - 二进制拆分)
将一个数二进制分解,例如:$13=2^0+2^1+2^2+6$
然后,将$13$个$W_i\ V_i$物品分解成$W_i\ V_i,\quad 2\times W_i\ 2\times V_i,\quad 4\times W_i\ 4\times V_i,\quad 6\times W_i\ 6\times V_i$
那么选择这些物品时就可以组合出$1 \to 13$之间的任意一种情况了。
同理任意一个$n$如此分解为$2^0+2^1+2^2+…+2^x+q$($q$为最后的剩余),然后就可以用这些数组合出$1 \to n$之间的所有数了
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
#define re register
int dp[100100];
int s[1000];
int ls;
int a[110],b[110];
signed main(){
int n,m;
while(233){
for(re int i=0;i<=m;i++) dp[i]=0;
ls=0;
scanf("%d%d",&n,&m);
if(n==0) break;
for(re int i=0;i<n;i++)
scanf("%d",&a[i]);
for(re int i=0;i<n;i++)
scanf("%d",&b[i]);
for(re int i=0;i<n;i++){
re int tt=0,tmp=1;
re int bfa=a[i];
while(tt+tmp<=b[i]){
s[ls++]=a[i];//加入新物品
tt+=tmp;
tmp<<=1;
a[i]<<=1;
}//分解物品为2^0+2^1+2^2...个
b[i]-=tt;
if(b[i]) s[ls++]=bfa*b[i];//最后的剩余量(如上面的6)
}
dp[0]=1;
for(re int i=0;i<ls;i++)
for(re int j=m;j>=s[i];j--)
dp[j]|=dp[j-s[i]];//简单背包即可
int cnt=0;
for(re int i=1;i<=m;i++) cnt+=dp[i];
printf("%d\n",cnt);
}
return 0;
}
开O2就可以了
测试数据好像更新了,试了一下,二进制优化也TLE了
二进制优化的HDU2844 AC了,POJ1742 T了
这道题的正解应该是 单调队列优化,二进制优化在 POJ 上是过不了的
%
我差点就看懂了
TQL