欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

题目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;
}
相关标签: 深度搜索