部分和问题算法 代码(C)

题目: 给定整数a1, a2, ..., an, 判断是否可以从中选出若干数, 使它们的和恰好为k.

解法很多, 最简单的解法是使用深度优先搜索, 时间复杂度O(2^n), 不是最优解法.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.13
 *本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>  

bool dfs (int i, int sum, int* a, int n, int k) {
    if (i==n) return sum == k;
    if(dfs(i+1, sum, a, n, k)) return true;
    if(dfs(i+1, sum+a[i], a, n, k)) return true;
    return false;
}  

void solve(int* a, int n, int k) {
    if (dfs(0,0,a,n,k)) printf("Yes\n");
    else printf("No\n");
}  

int main(void)
{
    const int MAX_N = 20;
    int a[MAX_N] = {1, 2, 4, 7};
    int n = 4, k = 13; //k位需要找到的数字  

    solve(a, n, k);  

    return 0;
}

输出:

Yes

作者：csdn博客 Mystra

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， return
， 代码
， dfs
， sum
解法
贪心算法背包问题代码、旅行商问题算法代码、tsp问题算法源代码、银行家算法c语言代码、sift算法c 源代码，以便于您获取更多的相关知识。