回溯，动态规划-求n个数中和为k的最少解

如题：给定若干正整数，从中选出若干数，使他们的和恰好为k，要求找选择元素最少的解

##动态规划
可以看成0-1背包问题，物品价值与重量为数本身，背包容量为k，网格中的值更新时需要记录是由哪些值所引起的改变。

0-1背包问题中，有三种可能情况，1：当前值等于正上面那个值 （背包容量小于该行重量）。2：当前值等于该行价值加上上面所需要的最优值，3：当前值等于正上面那个值（由max函数比较两个值相等，但是取的是正上面的值，记录路径需要当成第2种情况）

import java.util.ArrayList;
import java.util.Scanner;

/*
 * 给定若干正整数，从中选出若干数，使他们的和恰好为k，要求找选择元素最少的解（抽取不放回的选择）
 */
public class 给定若干正数和为k最少相加的 {

	public static void main(String[] args) {
		// 输入n代表有n个正整数，接着输入n个正整数，接着输入k代表求和
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int a[] = new int[n + 1];
		for (int i = 1; i <= n; i++)
			a[i] = in.nextInt();
		int key = in.nextInt();
		map[][] jj = new map[n + 1][key + 1];
		in.close();
		for (int i = 0; i < n + 1; i++)
			for (int j = 0; j < key + 1; j++) {
				map haha = new map();//这一步一定需要，切记
				jj[i][j] = haha;
				jj[i][j].i = 0;
			}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= key; j++) {
				if (j >= a[i]) {
					int temp = jj[i - 1][j - a[i]].i + a[i];
					jj[i][j].i = Math.max(jj[i - 1][j].i, temp);
					// 当前值等于等于上面那个值（由max函数比较两个值相等，但是取的是正上面的值，记录路径需要当成第2种情况）（第二个或的作用）
					if (jj[i][j].i == temp || jj[i - 1][j].i == temp) {
						ArrayList<Integer> tt = new ArrayList<Integer>();
						tt = copy(jj[i - 1][j - a[i]].nums);
						// tt=jj[i-1][j-a[i]].nums; //这里传的是地址给tt
						tt.add(a[i]);
						jj[i][j].nums = tt;
					} else { // 直接上面的值
						jj[i][j].nums = copy(jj[i - 1][j].nums);
					}
				} else {
					jj[i][j].i = jj[i - 1][j].i;
					jj[i][j].nums = copy(jj[i - 1][j].nums);
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= key; j++) {
				if (jj[i][j].i == key && jj[i][j].nums.size() > 1) {
					for (int t : jj[i][j].nums)
						System.out.print(t + " ");
					System.out.println();
				}

			}
		}

	}

	private static ArrayList<Integer> copy(ArrayList<Integer> nums) {
		ArrayList<Integer> aa = new ArrayList<Integer>();
		for (int i : nums)
			aa.add(i);
		return aa;
	}

	static class map {
		int i;
		ArrayList<Integer> nums = new ArrayList<Integer>(); //记录路径
	}

}

截图：

##回溯
解空间为子集树，每个数字只有取与不取的区别。

public class 给定若干正数和为k最少相加的a {
	static int[] a;     //n个数
	static int n;
	static int[] x;        //解向量
	static int target;      //k
	static int cSum;        

	private static void backtrack(int i) {
		if (i > n - 1) {
			if (target == cSum) {
				for (int j = 0; j < x.length; j++) {
					if (x[j] == 1)
						System.out.print(a[j] + " ");
				}
				System.out.println();
			}
		} else {
            //没有进行剪枝
			if (cSum + a[i] <= target) { // 第i个数取   
				x[i] = 1;
				cSum += a[i];
				backtrack(i + 1);
				cSum -= a[i];       //他还要进行不取，所以还要把他减回去
			}

			x[i] = 0;
			backtrack(i + 1);
		}
	}

	public static void main(String[] args) {
		int _a[] = { 1, 2, 3, 4, 5, 6 };
		int _tar = 5;

		a = _a;
		n = _a.length;
		x = new int[n];
		target = _tar;
		cSum = 0;
		backtrack(0);   

	}
}

截图：