重庆网站平台建设,网站开发建设收费标准,建设门户公司网站,网站文字链接集合里的乘法
题目描述
给定一个目标数T和一个整数集合S#xff0c;判断是否存在S的一个非空子集#xff0c;子集中的数相乘的积为T。
关于输入
输入为两行。 第一行为目标数T#xff0c;和S中的元素个数N#xff0c;以空格隔开。 第二行为S中的N个元素#xff0c;以空…集合里的乘法
题目描述
给定一个目标数T和一个整数集合S判断是否存在S的一个非空子集子集中的数相乘的积为T。
关于输入
输入为两行。 第一行为目标数T和S中的元素个数N以空格隔开。 第二行为S中的N个元素以空格隔开。 其中 N 16。
关于输出
如果可以则输出YES否则输出NO。
例子输入
12 5
1 2 3 4 5例子输出
YES解题分析
这个算法的核心思想是使用深度优先搜索DFS遍历所有可能的子集并计算它们的乘积。如果找到一个子集的乘积等于目标数就返回YES否则返回NO。
以下是该算法的详细步骤
1. 首先我们读取目标数T和集合S的元素。集合S的元素被存储在一个数组中数组的索引从0开始。
2. 然后我们调用深度优先搜索函数dfs开始时的索引为0乘积为1。这意味着我们从集合的第一个元素开始搜索初始的乘积是1因为任何数乘以1都等于它自己。
3. 在dfs函数中我们首先检查是否已经找到了解决方案flag是否为1或者当前乘积是否已经超过了目标数T。如果是的话我们就直接返回不再继续搜索。这是一种剪枝策略可以避免无效的搜索提高算法的效率。
4. 然后我们检查当前的乘积是否等于目标数如果是的话我们就设置flag为1并返回。这表示我们已经找到了一个满足条件的子集。
5. 如果当前的索引已经达到了集合的大小这意味着我们已经遍历了所有的元素但还没有找到满足条件的子集所以我们就返回。
6. 否则我们对当前索引的元素有两种选择一是选择它将它乘入当前的乘积二是不选择它保持当前的乘积不变。我们对这两种选择都进行搜索。这是深度优先搜索的核心步骤通过递归调用dfs函数我们可以遍历所有可能的子集。
7. 在主函数中如果flag为1说明我们找到了一个解决方案输出YES。否则输出NO。
这个算法的时间复杂度是O(2^n)其中n是集合的大小。因为对于集合中的每一个元素我们都有两种选择选择它或者不选择它。所以总共有2^n种可能的子集。由于题目中给出集合的大小不超过16所以这个算法在时间上是可行的。
代码实现
#include stdio.hint N;
long long T, S[16];
char flag;void dfs(int index, long long product) {if (flag || product T) return;if (product T) {flag 1;return;}if (index N) return;dfs(index 1, product * S[index]);dfs(index 1, product);
}int main() {scanf(%lld %d, T, N);for (int i 0; i N; i) {scanf(%lld, S[i]);}dfs(0, 1);if (flag) {printf(YES\n);} else {printf(NO\n);}return 0;
}
