体积

题目描述

【问题描述】
     给出 n 件物品，每件物品有一个体积 V i ，求从中取出若干件物品能够组成的不同的体积和有多少种可能。
【输入格式】
第 1 行 1 个正整数，表示 n。
第 2 行 n 个正整数，表示 V i ，每两个数之间用一个空格隔开。
【输出格式】
一行一个数，表示不同的体积和有多少种可能。
 

输入

输出

数据规模】
对于 30% 的数据满足：n≤5，V i ≤10。
对于 60% 的数据满足：n≤10，V i ≤20。
对于 100% 的数据满足：n≤20，1≤V i ≤50。

每个物品都有拿和不拿两种情况

#include<bits/stdc++.h>
using namespace std;
int n,v[30],a[1010];
void dfs(int dep,int sum){
	if(dep>n){
		a[sum]=1;
		return;
	}
	dfs(dep+1,sum+v[dep]);
	dfs(dep+1,sum);
}
int main(){
	int i,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&v[i]);
	}
	memset(a,0,sizeof(a));
	dfs(1,0);
	ans=0;
	for(i=1;i<=1000;i++) if(a[i]==1) ans++;
	printf("%d",ans);
	return 0;
}