題意:給你n個物品的體積和數量,讓你求有多少種組合能恰好裝滿M體積的背包
開始一直在想怎麼用一維數組來捉,弄了半天沒什麼結果。
所以回歸一般的DP,dp[i][j]表示前i種物品,組成j的容量有幾種組法
枚舉第i種物品的時候可以取一個,取兩個,。。,最後別忘了,也可以不取
[cpp]
#include<cstdio>
#include<cstring>
const int mod = 100000007;
const int maxn = 1010;
int dp[55][maxn];
int a[55],b[55];
int main()
{
int t,ca=1,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=b[i];k++)
{
if(j-k*a[i]>=0)
dp[i][j]+=dp[i-1][j-k*a[i]];
}
}
for(int j=0;j<=m;j++) dp[i][j]+=dp[i-1][j],dp[i][j]%=mod;
}
printf("Case %d: %d\n",ca++,dp[n][m]);
}
return 0;
}