本文主要是介绍回溯法 子集和问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述 :
子集和问题的一个实例为〈S,t 〉。其中,S={ X1 ,X2 ,…,Xn } 是一个正整数的集合,C是一个正整数。子集和问题判定是否存在S 的一个子集S1 ,使得∑X (X∈S1) = C。
编程任务 :
对于给定的正整数的集合S={ X1 ,X2 ,…,Xn } 和正整数C,编程计算S 的一个子集S1 ,使得∑X (X∈S1) = C。
数据输入 :
第1行是2个正整数n(n<400)和c,n表示S的大小,c是子集和的目标值。接下来的1行中,有n个正整数,表示集合S中的元素 。
结果输出:
输出有m行,每行是子集和问题的解输出,当问题无解时,输出“No Solution!”。
输入样例:(两组数据)
5 10
2 2 6 5 4
5 3
2 2 6 5 4
输出样例:
2 2 6
No Solution!
有可疑问,当时数据:
5 10
2 2 6 5 4
结果只有2 2 6,为什么没有 6 4?
本程序也输出了6 4
import java.util.Scanner;public class ZiJiHe {static int sum=0;static int c=0;static int n=0;static int[] arr;static int[] temp;static int t=0;public static void main(String[] args) {Scanner input=new Scanner(System.in);n=input.nextInt();c=input.nextInt();arr=new int[n];temp=new int[n];for (int i = 0; i < arr.length; i++) {arr[i]=input.nextInt();}search(0);input.close();if(t==0){System.out.println("No Solution!");}}public static void search(int m){if(sum==c){t=1;for (int i = 0; i < m; i++) {if(temp[i]==1){System.out.print(arr[i]+" ");}}System.out.println();return;}if(sum>c||m==n){return;}if(sum+arr[m]<=c){sum+=arr[m];temp[m]=1;search(m+1);temp[m]=0;sum-=arr[m];}search(m+1);}
}
这篇关于回溯法 子集和问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!