参考文章：
思路：
首先用数组weight存放重量，数组value存放价值，再使用二维数组v[][]存放动态规划的过程（如果是至少时，初始化为0,；如果是恰好时，初始化为负无穷大）。商品是从第一个往最后一个加，背包容量是从0开始到题目要求大小。若要打印对应商品，则从结果开始递推。
代码：
package text2; import java.util.Scanner; public class 背包问题_动态规划 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int capacity = scanner.nextInt(); int n = scanner.nextInt(); int weight[] = new int[n+1];//重量 int value[] = new int[n+1];//价值 for(int i=1;i<=n;i++) { weight[i] = scanner.nextInt(); } for(int i=1;i<=n;i++) { value[i] = scanner.nextInt(); } int v[][] = new int[n+1][capacity+1]; // Arrays.fill(v, 0); /** * 使用非递归方式，求解v[0 .. N][0 .. capacity]，即for循环从下至上求解 */ for(int i=0;i<=n;i++) for(int j=0;j<=capacity;j++) {//j表示背包容量 if(i==0 || j==0) v[i][j] = 0;//初始化边界 else { if(j<weight[i]) v[i][j] = v[i-1][j]; else { v[i][j] = Math.max(v[i-1][j], v[i-1][j-weight[i]]+value[i]); } } } //打印v的所有结果 for(int i = 0; i <= n; i++) { for(int j = 0; j <= capacity; j++) { System.out.print(v[i][j] + " "); } System.out.println(); } System.out.println("背包内最大的物品价值总和为：" + v[n][capacity]); //求解最大具体是有哪几个商品组成的 int item[] = new int[n+1]; // Arrays.fill(item, 0);// 下标i对应的物品若被选中，设置值为1 // 从最优解，倒推回去找 int t = capacity; for(int i=n;i>0;i--) { if(v[i][t]>v[i-1][t]) { item[i] = 1; t = t-weight[i]; } } System.out.print("包内物品的编号为："); for (int i = 0; i < n + 1; i++) { if (item[i] == 1) { System.out.print(i + " "); } } } }
