背包问题

题目：在n个数字中取出m个数字，使m个数字之和为b，请打印所有方案。

例：在{6, 5, 4, 3, 2, 1}中取m个数字，使数字之和为5，请打印所有方案。

解：

import java.util.ArrayList;import java.util.Arrays;/** * Created by LH on 2017/3/2. */public class Pack {    int[] a;    int best;    ArrayList<Integer> res = new ArrayList<>();    //搜索（递归）    public void seach(int i, int ibest) {        if (i == a.length) {            if (ibest == best) {                //打印结果                System.out.PRintln(res);            }            return;        }        if (ibest + a[i] <= best) {            Integer index = new Integer(a[i]);            res.add(index);            seach(i + 1, ibest + a[i]);            res.remove(index);        }        seach(i + 1, ibest);    }    //递推    public void pack01() {        Arrays.sort(a);        int[][] f = new int[a.length + 1][best + 1];        for (int i = 1; i <= a.length; i++) {            for (int j = 0; j <= best; j++) {                f[i][j] = (i == 1 ? 0 : f[i - 1][j]);                if (j >= a[i - 1]) {                    f[i][j] = Math.max(f[i][j], f[i - 1][j - a[i - 1]] + a[i - 1]);                }            }        }        //打印结果        for (int k = Math.min(a.length, best); k > 0; k--) {            int i = k;            int j = best;            if (f[i][j] == best) {                while (i > 0) {                    if (j >= a[i - 1] && f[i][j] == f[i - 1][j - a[i - 1]] + a[i - 1]) {                        System.out.print(a[i - 1] + " ");                        j -= a[i - 1];                    }                    i--;                }            }            System.out.println();        }    }    public static void main(String[] args) {        //初始化        Pack pack = new Pack();        pack.a = new int[]{6, 5, 4, 3, 2, 1};        pack.best = 5;        //搜索        pack.seach(0, 0);        //递推        pack.pack01();    }}