原题链接
考察:背包dp
yxc:没做出来本题的反思自己有没有认真听基础课
我:菜狗不配()
思路:
??dfs写的,当时觉得铁TLE,但是没有想到别的做法(.)
??f[i][j]表示前i个物品重量为j是否能实现.
dp方程:
f[i][j] = f[i-1][j]
f[i][j] = f[i-1][j+w[i]]
f[i][j] = f[i-1][j-w[i]]
??下标为负直接偏移就行了
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110,M = 100010;
int w[N],n,cnt;
bool f[N][M<<1];
int main()
{
scanf("%d",&n);
int sum = 0;
for(int i=1;i<=n;i++) scanf("%d",&w[i]),sum+=w[i];
f[0][sum] = 1;
for(int i=1;i<=n;i++)
for(int j=0;j<=2*sum;j++)
{
f[i][j] = f[i-1][j];
if(j+w[i]<=2*sum) f[i][j] = max(f[i][j],f[i-1][j+w[i]]);
if(j-w[i]>=0) f[i][j] = max(f[i][j],f[i-1][j-w[i]]);
}
for(int i=sum+1;i<=2*sum;i++)
cnt += f[n][i];
printf("%d\n",cnt);
return 0;
}