二进制优化原理

基本思想:

任意10进制数n,把它分开,想快速找到其中数字(1-n)的组合,最简单的方法是分成n个1,这样可以形成任意的组合数(1–n)但是这样很慢,最多要取n次!!同时我们知道,任何10进制数都能拆成二进制数的组合(2^j),如:

$$15 = 1111 = 2^3+2^2+2^1+2^0$$
$$14 = 1110 = 2^3+2^2+2^1$$

我们可以看到 任何 10进制数 都可以由$2^j$的组合形成,反过来想你有一些$2^J$数,可不可以组合一定范围内的任意数,如:组合成1000内的任意数,包括1000,要求这些$2^j$的数加起来不能超过1000

更容易理解:

如果你有1000个苹果,想要快速的取$n (n<=1000)$个苹果,怎么做?

想法一:

分成1000堆苹果,每堆一个苹果,可以取出任意1000内的苹果数,最坏情况要取1000次

想法二:

分成10堆:

$$2^0,2^1,2^2,2^3,2^4,2^5,2^6,2^7,2^8,489$$

也就是

$$1,2,4,8,16,32,64,128,256,489$$

其中486是最后剩余的数,想一想能不能利用上面的10堆组合成1000进制内的任何数!!!!

总结

把一个数n分成1,2,4,8…$2^j$和$n-(1+2+4+8…+2^J)$,这样能组合成n内,包括n内的任意数
通常用于多重背包的优化.

代码:

#include <cstdio>

int main(){

    int n;
    scanf("%d",&n);

    int cnt=0;
    int s=0;
    //写法一:
    while( n >=(1<<cnt)){
        printf("%d ",(1<<cnt));
        n = n-(1<<cnt);
        cnt++;

    }
    if(n>0)
        printf("%d",n);

    printf("\n");
    //写法二:
    int i;
    scanf("%d",&n);

    for(i=0;i<=1000;i++){
        if(n >= (1<<i))//如果余数比 要分下来的数大
        {
            printf("%d ",(1<<i));
            n=n-(1<<i);
        }
        else{
            printf("%d",n);
            break;
        }


    }

    return 0;
}