对于有n种物品，每种mi件，背包容量为 v 的多重背包，如果直接转化成01背包，时间复杂度为∑mi*v，显然当两者乘积太大时，TLE无疑。现在有一种对用二进制减小∑mi的优化方法。
对于一种有mi件，体积为vi的商品，可以用 k+2种 体积分别为(1<<0)*vi,(1<<1)*vi . . . . . .(1<
(1<<0),(1<<1) . . . . . .(1<
例如 mi = 13，则可分解成 1，2，4，和一个 6。
也就是说对于一种有mi件的商品可以分解成有（k+2）种只有一件的商品来代替。显然(k+2) <= mi恒成立，且mi越大这种优化效果越明显。
#include#include #include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) #pragma comment(linker,"/STACK:102400000,1024000") using namespace std; bool ans[120010]; int main() { //freopen("asdfas.txt","w",stdout); int i,k,j,a[6],sum,t,s; bool mark = true; int icase = 1; while(1) { for(sum = 0,i = 0,mark = false;i < 6; ++i) { scanf("%d",&a[i]); if(a[i]) { mark = true; sum += a[i]*(i+1); } } if(mark == false) return 0; printf("Collection #%d:\n",icase++); if((sum&1) == 0) { sum >>= 1; memset(ans,false,sizeof(bool)*(sum+3)); ans[0] = true; for(i = 0;i < 6; ++i) { a[i] = min(a[i],sum/(i+1)); } for(i = 0;i < 6; ++i) { if(a[i]) { for(j = (a[i]>>1),t = 1;t <= j;t <<= 1) { s = t*(i+1); for(k = sum;k >= s; --k) { if(ans[k-s]) ans[k] = true; } } for(k = sum,j = (a[i]-t+1)*(i+1);k >= j; --k) { if(ans[k-j]) ans[k] = true; } } } if(ans[sum]) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } else { printf("Can't be divided.\n\n"); } } return 0; }