B、智乃买瓜

简单背包，简单来讲，这道题的题解就写在题面里边了。

1.购买一整个重量为$w_{i}w\_i$的西瓜

2.把瓜劈开，购买半个重量为$\frac{w_i}{2}\backslash frac\{w\_i\}\{2\}$的西瓜

3.不进行购买操作

对应着DP转移的三个决策，不妨开一个$dp[N][M]dp[N][M]$的数组，$dp[i][j]\mathrm{表}dp[i][j]表$示现在放到第$ii$个西瓜，且当前的重量为$jj$。

显然有DP转移方程：

$dp[0][0]=1dp[0][0]=1$

$dp[i][j]=dp[i-1][j-w_i]+dp[i-1][j-\frac{w_i}{2}]+dp[i-1][j]dp[i][j]=dp[i-1][j-w\_\{i\}]+dp[i-1][j-\backslash frac\{w\_i\}\{2\}]+dp[i-1][j]$

注意当或者时这一项是没有的。

当然，实际处理的时候习惯将二维数组用滚动数组优化成一维。

时间复杂度$O(NM)O(NM)$，空间复杂度$O(N)O(N)$

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int n,m,x;
const long long mod=1e9+7;
long long dp[MAXN]; 
int main()
{
	dp[0]=1;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		for(int i=m;i;--i)
		{
			if(i>=x/2)dp[i]+=dp[i-x/2];
			if(i>=x)dp[i]+=dp[i-x];
			while(dp[i]>=mod)dp[i]-=mod;
		}
	}
	for(int i=1;i<=m;++i)
	{
		printf("%lld%c",dp[i]," \n"[i==m]);
	}
	return 0;
}