题意：bool多重背包
分析：学了种很快的新方法，就是每次填f[j]时直接由f[j-weight[i]]推出，前提是num[j - weight[i]]<sum[i]num每填一行都要清零，num[j]表示当前物品填充j大小的包需要至少使用多少个
但是使用这种方法有一个条件，就是要求f数组只能是bool类型。否则会出错。
对于bool型则不会有性价比的问题，只有体积可达和不可达的问题，在可达前提下只要尽量少的使用当前物品即可，value型则不行，可达不一定少用当前物品，因为多用当前物品可能会获得高价值。 例如，如果当前物品性价比极高，那么对于任意大小的包都应该尽量多的当前物品以追求高价值，用上述方法会使得后面包容量足够大时，会有些位置（j=(sum[i]+1)*weight[i]）因无法满足条件num[j - weight[i]]<sum[i]（即之前已经把当前物品买完），而无法购买当前物品。
View Code #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > using namespace std; #define maxn 105 #define maxm 100005 bool f[maxm]; int used[maxm], num[maxn], value[maxn]; int n, m; void input(){ for ( int i = 0 ; i < n; i ++ ) scanf( " %d " , & value[i]); for ( int i = 0 ; i < n; i ++ ) scanf( " %d " , & num[i]);} void work(){ memset(f, 0 , sizeof (f)); f[ 0 ] = true ; int sum = 0 ; for ( int i = 0 ; i < n; i ++ ) { memset(used, 0 , sizeof (used)); for ( int j = value[i]; j <= m; j ++ ) if ( ! f[j] && f[j - value[i]] && used[j - value[i]] < num[i]) { f[j] = true ; used[j] = used[j - value[i]] + 1 ; sum ++ ; } } printf( " %d\n " , sum);} int main(){ // freopen("t.txt", "r", stdin); while (scanf( " %d%d " , & n, & m), n | m) { input(); work(); } return 0 ;}