DFS-体积

2024-01-07 19:31:43

DFS-体积

题目:
给出n件物品,每件物品有一个体积Vi,求从中取若干件物品能够组成不同的体积和有多少种可能。例如,n=3,Vi=(1,3,4),那么输出6,6种不同的体积分别为1,3,4,5,7,8
输入格式:
第一行一个正整数,表示n。

    第二行n个正整数,表示Vi,每两个数间用一个空格隔开。

输出格式:
一行一个数,表示有多少种可能

输入样例
3

    1 3 4

输出样例
6

数据规模
n ≤ 20,1 ≤ Vi ≤ 50

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include<iostream>
using namespace std;

const int N = 25;
const int M = 1005;
int v[N];
bool hash[1001];
int n, num;//全局变量默认为0

//深搜 
void dfs(int dep,int sum){
	if(dep > n){
		hash[sum] = true;
		return;
	}
	dfs(dep+1,sum+v[dep]);
	dfs(dep+1,sum);
} 
 
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) 
	{
		cin >> v[i];
	}
	dfs(1,0);
	for(int i=1; i<=1000; i++)
	{
		if(hash[i]) num++;
	}	
	cout << num << endl;
	return 0;
}

文章来源:https://blog.csdn.net/Chow_Ssehc/article/details/135428149
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。