Time Limit: 10 second
Memory Limit: 2 MB

問(wèn)題描述
子集和問(wèn)題的一個(gè)實(shí)例為〈S,C 〉。其中，S={ X1 ，X2 ，…，Xn } 是一個(gè)正整數(shù)的集合，C是一個(gè)正整數(shù)。
編程任務(wù) ：對(duì)于給定的正整數(shù)的集合S={ X1 ，X2 ，…，Xn } 和正整數(shù)C，編程計(jì)算S 的一個(gè)子集S1 ，使得∑X (X∈S1) = C(子集s1的和等于c)

Input

第一行有2個(gè)正整數(shù)n和c，n表示s集合中元素的個(gè)數(shù)，c是子集和的目標(biāo)值。第二行有n個(gè)正整數(shù)，表示集合s中的元素

Output

輸出一行數(shù)據(jù)，是子集和問(wèn)題的解，當(dāng)問(wèn)題無(wú)解時(shí)，輸出"No Solution!".（有解時(shí)，在解的后面多添加一個(gè)空格和一個(gè)換行符）

Sample Input

5 10 2 2 6 5 4

Sample Output

2 2 6 ?

【題解】

用一個(gè)sum來(lái)累加當(dāng)前選擇的數(shù)。深搜下就可以了。用過(guò)的數(shù)不能再用，sum > c后剪枝。還有一個(gè)剪枝就是所有的數(shù)加起來(lái)仍然<c，這種時(shí)候直接輸出無(wú)解信息就可以了。

【代碼】

#include <cstdio> #include <stdlib.h>int n,c,a[5000],sum = 0,num = 0,ans[5001]; bool bo[5001];void input_data() {scanf("%d %d",&n,&c); //輸入n 和 cfor (int i = 1;i <= n;i++)scanf("%d",&a[i]),sum+=a[i]; //累加a[i]的和if (sum < c) //如果所有數(shù)之和仍小于c則輸出無(wú)解信息。{printf("No Solution!");exit(0);}if (sum == c) //如果所有的數(shù)剛好等于答案 則直接輸出所有的數(shù){for (int i = 1;i <= n;i++)printf("%d ",a[i]);exit(0);}sum = 0; //這里的sum用于搜索時(shí)候的累加for (int i = 1;i <= 5000;i++) //所有的數(shù)一開(kāi)始都可以用bo[i] = true; }void output_ans() {for (int i = 1;i <= num;i++) //輸出答案printf("%d ",ans[i]); }void sear_ch(int t,int m) //t表示這個(gè)數(shù)的數(shù)值，m是這個(gè)數(shù)的下標(biāo) {bo[m] = false; //標(biāo)記這個(gè)數(shù)已經(jīng)使用過(guò)sum += t; //累加當(dāng)前選擇的數(shù)字ans[++num] = t; //記錄答案。if (sum == c) //如果累加和符合要求則輸出答案。{output_ans();exit(0);}if (sum < c) //如果sum小于c則繼續(xù)搜素，否則不搜索了 返回上一層for (int i = 1;i <= n;i++)if (bo[i]) //如果這個(gè)數(shù)字未被使用sear_ch(a[i],i);sum -= t; //回溯num--;bo[m] =true; }void get_ans() {for (int i = 1;i <= n;i++)sear_ch(a[i],i);printf("No Solution!"); //最后還要再輸出一次無(wú)解信息。 }int main() {input_data();get_ans();return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的【9502】子集问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。