学步园

题意：输入n1~n6 代表1~6的 个数，然后求这些数能不能通过分配达到value相等的状态

思路：多重背包（详见背包九讲） 能不能装满背包v/2的问题 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[100000];
int v;
bool flag;
void _com(int c , int w) {
    for(int i = 0 ; i <= v ; i ++) {
        if(i - c >= 0) 
        dp[i] = max(dp[i] , dp[i - c] + w);
        if(dp[v] == v) {
            flag = true;
            return;    
        }    
    }    
}
void _01(int c , int w) {
    for(int i = v ; i >= 0 ; i --) {
        if(i - c >= 0)
        dp[i] = max(dp[i] , dp[i - c] + w);
        if(dp[v] == v) {
            flag = true;
            return;    
        }    
    }    
}
void _mul(int c , int w , int cnt) {
    if(c*cnt>=v) {   //如果满足条件就完全背包 
        _com(c , w);
        return;        
    }  
    int k = 1;
    while(k < cnt) { //否则就二进制优化  
        _01(k*c , k*w);
        cnt -= k; 
        k = 2*k;   
    }
    _01(cnt*c , cnt*w);
}
int main() {
    int n[7];   
    int cas = 1; 
    while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6]) {
        if(!n[1] && !n[2] && !n[3] && !n[4] && !n[5] && !n[6]) break;
        flag = false;
        v = 0;
        for(int i = 1 ; i <= 6 ; i ++) {
            v += i*n[i];    
        }
        if(v%2==1) {      //偶数肯定不行 
            printf("Collection #%d:\n",cas++);
            printf("Can't be divided.\n\n");
            continue;        
        }
        v /= 2;
        memset(dp , 0 , sizeof(dp));
        for(int i = 1 ; i <= 6 ; i ++) {
            _mul(i , i , n[i]);
            if(flag) break;    
        }
        printf("Collection #%d:\n",cas++);
        if(flag) printf("Can be divided.\n\n");
        else printf("Can't be divided.\n\n");
    }
}