設集合S={x1,x2,…,xn}是一個正整數集合，c是一個正整數，子集和問題判定是否存在S的一個子集S1，使S1中的元素之和為c，試設計一個解子集和問題的回溯法，
輸入格式:
輸入資料第1行有2個正整數n和c，n表示S的大小，c是子集和的目標值，接下來的1行中，有n個正整數，表示集合S中的元素， 是子集和的目標值，接下來的1 行中，有n個正整數，表示集合S中的元素，
輸出格式:
輸出子集和問題的解，以空格分隔，最后一個輸出的后面有空格，當問題無解時，輸出“No Solution!”，
輸入樣例:
在這里給出一組輸入，例如：
5 10
2 2 6 5 4
輸出樣例:
在這里給出相應的輸出，例如：
2 2 6
本題要求只輸出第一個解，并采用回溯法，所以可以主體來列舉所有情況，然后再剪枝剪掉不需要的分支：
package 宿題;
import java.io.*;
public class PTASubsetSum {
static int c;
static int n;
static boolean Out=true;//這里新建一個標記位，用來記錄有無第一個解出現，結束遞回；
public static void main(String args[])throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));//當需要輸入大量資料時BufferedReader處理速度快，比Scanner高效；
in.nextToken();
n=(int)in.nval;
in.nextToken();
c=(int)in.nval;
int a[]=new int[n];
int SUM=0;
for(int i=0;i<n;i++){
in.nextToken();
a[i]=(int)in.nval;
SUM+=a[i];//減去當所有數和小于c時的分支；
}
if(SUM>=c){
Count(a,0,0,"");
if(Out)
System.out.println("No Solution!");
}else
System.out.println("No Solution!");
}
private static void Count(int a[],int count,int sum,String s){
if(count<n&&Out){
if(sum+a[count]==c){
Out=false;//結束遞回；
System.out.println(s+a[count]+" ");
}else if(sum+a[count]<c){//分支向下求解；
Count(a,count+1,sum+a[count],s+a[count]+" ");
System.out.println(s+a[count]+" ");
}
Count(a,count+1,sum,s);
System.out.println(s);
}
}
}
該演算法最壞情形下時間復雜度為O(2^n)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122749.html
標籤：其他
下一篇：OpenGL圖片拼接扭曲成圓