图解四种常见背包问题及优化方式-创新互联

比如要枚举0->1023中所有的数能不能凑成其中任意一个数
我们平常的枚举方法就是：0,1,2,3,4,5,…,1023。这样枚举1024次
使用二进制枚举优化，就可以只需枚举10次就可以枚举出任意一个数。
将0~1023这1024个数分为10个组，
每组分别是：1 2 4 8 16 32 64 128 256 512 这10个数字(2^0 2^1 2^2 … 2^9)。
在枚举的时候只枚举这10个数字，选或不选。就可以枚举出0~1023中的任意一个数字

#include#include

using namespace std;

const int N = 25000;

int n,m;
int v[N],w[N];
int f[N];

int main() {cin >>n >>m;
    int cnt = 0;
    for (int i = 1; i<= n; i++) {int a,b,s;
        cin >>a >>b >>s;
        int k = 1;
        while(k<= s) {cnt++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if(s >0) {cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= v[i]; j--)
          f[j] = max(f[j],f[j-v[i]] + w[i]);
          
    cout<< f[m]<< endl;
    return 0;
}

只要是上一层推导的，则从后往前
如果是同层推导的，则从前往后
只要是由上层某个方向定向推来的，就可以进行状态压缩

#include#include

using namespace std;

const int N = 110;

int v[N][N],w[N][N],s[N];
int f[N];
int n,m;

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) {cin >>s[i];
        for(int j = 1; j<= s[i]; j++) {cin >>v[i][j] >>w[i][j];
        }
    }
    
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= 0; j--)
           for(int k = 1; k<= s[i]; k++)
              if(j >= v[i][k]) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<< f[m]<< endl;
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧