题目1058:部分和问题
程序员文章站
2022-05-24 09:09:05
...
题目链接:
http://acm.nyist.net/JudgeOnline/problem.php?pid=1058
描述
给定整数a1、a2、…….an,判断是否可以从中选出若干数,使它们的和恰好为K。
输入
首先,n和k,n表示数的个数,k表示数的和。
接着一行n个数。
(1<=n<=20,保证不超int范围)
输出
如果和恰好可以为k,输出“YES”,并按输入顺序依次输出是由哪几个数的和组成,否则“NO”
样例输入
4 13 1 2 4 7 |
样例输出
YES 2 4 7 |
算法思想:
这道题要求如果和恰好可以为k时,输出“YES”,且并按输入顺序依次输出是由哪几个数的和组成,故不能使用别的贪心算法之类的。
这是一道简单的深度搜索,给定的数要么取,要么不取,直接深度搜索就可以遍历所有的情况。(每次提交都完了加#include 头文件,没谁了。。。)
源代码
/*
Authoer:杨林峰
Date:2017.10.14
NYOJ(1058):部分和问题
*/
#include <iostream>
#include <cstring>
using namespace std;
int n, k, a[25], vis[25], ko;
/*深度搜索*/
void DFS(int i, int s)
{
//退出条件
if (ko) return;
if (s == k)
{
ko = 1;
cout << "YES" << endl;
for (int i = 0; i < 25; i++)
{
if (vis[i])
cout << a[i] << " ";
}
cout << endl;
return;
}
if (s > k) return;
if (i >= n)return;
int tmp = s; //记忆上次s值
vis[i] = 1; //取当前数,更新s和vis[]记录数组
s += a[i];
DFS(i + 1,s);
vis[i] = 0; //不取当前数,更新s和vis[]记录数组
s = tmp; //不取当前数,需回溯
DFS(i + 1, s);
}
int main()
{
while (cin >> n >> k)
{
memset(a, 0, sizeof(a));
memset(vis, 0, sizeof(vis));
ko = 0;
for (int i = 0; i < n; i++)
cin >> a[i];
DFS(0, 0);
if (ko == 0)
cout << "NO" << endl;
}
return 0;
}
下一篇: 【深度搜索】数独
推荐阅读
-
题目:猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半, 还不瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了 一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上 想
-
【程序21】 题目:猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个 第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下 的一半零一个。到第10天早
-
Android BugReport的组成部分和常见问题(详细说明)
-
蓝桥题目:B-27、2n皇后问题
-
浙大版《数据结构(第2版)》题目集 实例1.1 最大子列和问题 (20分)
-
React Native 前端面试题目汇总,高频问题,提薪必会
-
浙大版《C语言程序设计(第3版)》题目集习题4-2 求幂级数展开的部分和 (20分)
-
浙大版《C语言程序设计(第3版)》题目集练习4-3 求给定精度的简单交错序列部分和 (15分)
-
http://acm.hdu.edu.cn/showproblem.php?pid=3547昨天比赛的题目;立方体顶点染色有关问题
-
题目1058:部分和问题