【多重背包】Transport Ship

【来源】

　　2018年焦作网络赛

【参考博客】

　　https://blog.csdn.net/baymax520/article/details/82719454 

【题意】

　　有N种船只，每种船只的载货量为v[i]，每种船只有2^c[i]-1种，有q次询问，每次问有多少种载货方式填满容量s。

【思路】

　　如果用裸的01背包的话时间复杂度是O(N*2^c[i]*10000)，显然是会超时的，但是我们可以把每一种船只合并，比如船只有2^x-1艘的话，就拆成2^0+2^1+2^2+...+2^(x-1)，1~2^x-1的任意一个数都可以由拆分出来的数组成，将所有合并后的结果进行一次01背包即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M = 1e4+5;
const int mod = 1e9+7;
ll dp[M],v[25],c[25],V;
int main()
{
    int t,n,Q,s;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&Q);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&v[i],&c[i]);

        memset(dp,0,sizeof dp );
        dp[0] = 1 ;
        for(int i=1;i<=n;i++){
            for(int k=0;k<c[i];k++){
                V = 1ll* v[i] << k ;
                for(int j=M-1;j>=V;j--){
                    dp[j] += dp[j-V];
                    dp[j] %= mod ;
                }
            }
        }
        for(int i=1;i<=Q;i++){
            scanf("%d",&s);
            printf("%lld
",dp[s]);
        }
    }
    return 0;
}