01背包的变种

解题思路:当我看到这题的第一眼立马就想到了dfs在没有使用记忆化搜索是只拿了45分，于是开始了dp，在看了一些大佬的讲解后，明白了这个01背包的变种问题，

我们把题目看成这样，有一个容量为max（砝码总重量）的背包，每个砝码就是一件商品，你要做的不是选出价值最大的选法，而是去探讨选任意多砝码看看能剩下多少空间，话已至此，请自己想想看吧

注意事项:减去重量时要加绝对值

参考代码:

#include<stdio.h>

#include<math.h>

int w[1000],dp[1000][10000],ans;

int main(){

int n,sum=0;

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d",&w[i]);

sum+=w[i];

}

dp[0][0]=1;

for(int i=1;i<=n;i++){

for(int j=sum;j>=0;j--){

dp[i][j]=dp[i-1][j]||dp[i-1][abs(j-w[i])]||dp[i-1][abs(j+w[i])];

}

}

for(int i=1;i<=sum;i++){

if(dp[n][i]==1){

ans++;

}

}

printf("%d",ans);

return 0;

}