回溯法：子集和问题

问题：

????? 给定n个正整数wi和一个正整数m，在这n个正整数中找出一个子集，使得子集中的正整数之和等于m。

?

解的形式：

????? 设定一个n元组(x0,x1,...xn-1)，如果wi包含在这个子集中，xi就等于1，反之等于0.

?

BoundFunction：

?

算法伪代码：

?

/** *  */package com.iteye.caoruntao.sumofsub;/** * @author caoruntao * */public class SumOfSub {private int w[];private int m;private int x[];public SumOfSub(int w[], int m, int n){this.w = w;this.m = m;this.x = new int[n];}public void computeSumOfSub(int s, int k, int r){x[k] = 1;if(s+w[k] == m){printResult(k);System.out.println("*************");}else if(s+w[k]+w[k+1] <= m){computeSumOfSub(s+w[k],k+1,r-w[k]);}if(s+r-w[k]>=m && s+w[k+1]<= m){x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);}}public void printResult(int k){for(int i=0; i<=k; i++){if(x[i] == 1){System.out.println(i+1);}}}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubint w[] = new int[]{7,11,13,24};SumOfSub sumOfSub = new SumOfSub(w,31,4);int r = 0;for(int i=0; i<4; i++){r += w[i];}sumOfSub.computeSumOfSub(0, 0, r);}}

?
?

?