怎样做付费下载的网站,建设网站的运行费包括什么,网络营销的优势是什么,室内设计师经常用的网站题干#xff1a;
给出N个正整数组成的数组A#xff0c;求能否从中选出若干个#xff0c;使他们的和为K。如果可以#xff0c;输出#xff1a;Yes#xff0c;否则输出No。
Input
第1行#xff1a;2个数N, K, N为数组的长度, K为需要判断的和(…题干
给出N个正整数组成的数组A求能否从中选出若干个使他们的和为K。如果可以输出Yes否则输出No。
Input
第1行2个数N, K, N为数组的长度, K为需要判断的和(2 N 201 K 10^9) 第2 - N 1行每行1个数对应数组的元素Aii (1 Aii 10^6)
Output
如果可以输出Yes否则输出No。
Sample Input
5 13
2
4
6
8
10
Sample Output
No
解题报告 很多人说这题用背包但是我一直想不通1e9的空间是怎么用的背包。。。这题数据量20显然是搜索啊复杂度o(2^n)不怂不到30行就搞定了。 如果要写背包的话思路上也是可以的因为每个背包体积1e620个加起来也才2e8并且dp[j]val这里可以保证jvalj因为物品的体积和价值是相同的啊。所以直接跑恰好装满问题并且dp[k]k就可以了。只要数组开的下背包也不难写。
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;
ll n,k;
ll a[55];
bool dfs(ll step,ll cur) {if(cur k) return 1;if(step n) return 0;if(cura[step1] k) {if(dfs(step1,cura[step1])) return 1;}if(dfs(step1,cur)) return 1;return 0;
}
int main()
{cinnk;for(int i 1; in; i) cina[i];sort(a1,an1); if(dfs(0,0)) puts(Yes);else puts(No);return 0 ;
}
总结搜索题一定要注意啊需要从(0,0)这个状态开始搜索因为你直接(1,a[1])传入参数了那 不选第一个数 这个状态就被没有搜啊。。。
