博客打卡-0/1背包问题，回溯法

题目如下：

0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求重量和恰好为W具有最大的价值。

输入格式:

第一行输入背包载重量W及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。

输出格式:

第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入，输出: No，第二行输出背包内的物体总价值。

输入样例1:

5 10
2 6
2 3
6 5
5 4
4 6

输出样例1:

1 2 3 
14

输入样例2:

2 10
11 2
13 100

输出样例2:

No
0

解答思路如下：

本题是典型的 0/1 背包问题，要求在背包容量恰好装满的情况下，选取物品使得总价值最大。解题思路为使用 回溯法结合分支限界进行剪枝：从第一个物品开始深度优先尝试每一种可能的选取方式，若当前装入物品总重量不超过背包容量，则继续递归；同时利用 Bound 函数估计后续物品的最大价值，若估计值不大于当前最优解，则剪枝以减少搜索空间，提高效率。过程中记录使总价值最大的物品编号和对应价值，最终输出所选物品及总价值。若没有满足条件的组合，则输出 "No" 及 0。 

具体代码如下：

import java.util.Scanner;public class Main {static int C, N;static int[] w = new int[105];static int[] v = new int[105];static int cw = 0;static int cv = 0;static int len = 1;static int best_len = 1;static int best = 0;static int[] result = new int[105];static int[] best_result = new int[105];static int Bound(int i) {int rw = C - cw;int value = cv;while (i <= N && w[i] <= rw) {rw -= w[i];value += v[i];i++;}if (i <= N) {value += v[i] / w[i] * rw;}return value; }static void dfs(int k) {if (k > N && cw == C && cv > best) {best = cv; best_len = len;for (int i = 1; i < len; i++) {best_result[i] = result[i];} return;    }if (cw + w[k] <= C) {cw += w[k];cv += v[k];result[len] = k;len++; k++; dfs(k); k--;len--;result[len] = 0;cw -= w[k];cv -= v[k];}if (Bound(k + 1) > best) {k++;dfs(k);k--; }}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);N = scanner.nextInt();C = scanner.nextInt();for (int i = 1; i <= N; i++) {w[i] = scanner.nextInt();v[i] = scanner.nextInt();}dfs(1); if (best == 0) {System.out.println("No");System.out.println(0);}else {for (int i = 1; i < best_len; i++) {System.out.print(best_result[i] + " ");}System.out.println();System.out.println(best);}}
}

提交结果如下：