Exhaustive Search
Question
Write a program which reads a sequence A of n elements and an integer M, and outputs “yes” if you can make M by adding elements in A, otherwise “no”. You can use an element only once.
You are given the sequence A and q questions where each question contains Mi.
Input In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.
Output For each question Mi, print yes or no.
Constraints n ≤ 20 q ≤ 200 1 ≤ elements in A ≤ 2000 1 ≤ Mi ≤ 2000 Sample Input 1 5 1 5 7 10 21 8 2 4 17 8 22 21 100 35 Sample Output 1 no no yes yes yes yes no no
Meaning
从数组A中需拿出任意几个元素相加判断是否能得到给定的值Mi,如果可以输出yes,否则输出no
Sloution
首先,题目中的值n很小,那就直接递归给所有值全部列出来吧,也只是2的n次方。
Coding
#include<iostream>
using namespace std;
int A[25];
int n;
int solve(int i ,int tmp) {
if (tmp == 0)
return 1;
if (i >= n)
return false;
int res = solve(i + 1, tmp) || solve(i + 1, tmp - A[i]);
//针对于A[i],有选或者不选的权力这样一直递归下去,当tmp=0时候,返回真
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> A[i];
int t; cin >> t;
while (t--) {
int tmp; cin >> tmp;
if (solve(0, tmp))
cout << "yes" << endl;
else
cout << "no" << endl;
}
}
Summary
递归函数中重复调用了两个递归函数,算法复杂度为0(2的n次方)。。。
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接:Exhaustive Search
相关文章
- TinEye Reverse Search Engine_tidb和mysql
- AWS工程师辞职创建Tensor Search引擎,即插即用HuggingFace版CLIP模型
- javascript正则表达式总结(test|match|search|replace|split|exec)
- Search - 一文入门ElasticSearch(节点、分片、CRUD、倒排索引、分词)
- 最强大的 WordPress 搜索插件:Search Everything
- WordPress 批量替换插件 Search & Replace 和中文包
- ORA-19512: file search failed ORACLE 报错 故障修复 远程处理
- ORA-28277: LDAP search, while authenticating global user with passwords, failed. ORACLE 报错 故障修复 远程处理
- ORA-32480: SEARCH and CYCLE clauses can only be specified for recursive WITH clause elements ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-011780; Symbol: ER_LDAP_AUTH_SEARCH_USER_GROUP_ATTR_NOT_FOUND; SQLSTATE: HY000 报错 故障修复 远程处理
- MySQL Error number: MY-011799; Symbol: ER_LDAP_AUTH_USER_GROUP_SEARCH_FAILED; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-07586: spdcr: $SEARCH failure ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-013237; Symbol: ER_LDAP_AUTH_USER_GROUP_SEARCH_ROOT_BIND; SQLSTATE: HY000 报错 故障修复 远程处理
- Search in Rotated Sorted Array II详解程序员
- Search a 2D Matrix II详解编程语言
- Elastic search 6.0.0 正式发布 大量新特性
- location.search在客户端获取Url参数的方法
- php数组查找函数in_array()、array_search()、array_key_exists()使用实例