解题思路:
解决背包问题,首先要看通俗背包如何解决,0-1背包为全背包中一种比较特殊的背包问题。区别于单个物品的取出问题。下面将黏贴两份代码,分别为全背包问题的代码以及0-1背包的问题代码。
值得说的是背包问题实质是动态规划的典型问题,需要了解动态规划的两个特征1。子问题的划分2.子问题的重叠。
本题按照从下至上的探查方式,构造的一个逻辑表是求解的关键
用一案例重点解读:
n=3 w=5
w={2,3,4}v={3,5,7}
注意事项:
参考代码:
n\v 1 2 3 4 5
1 0 3 3 6 6
2 0 3 5 6 8
3 0 3 5 7 8
全背包:
import java.util.*; import java.math.*; //背包问题之全背包 public class 背包问题 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int v = 0;// 价值 int w = sc.nextInt();// 最大重量 int n = sc.nextInt();// 物品总量 int jiazhi[] = new int[n + 1]; int zhongliang[] = new int[n + 1]; int out[] = new int[n + 1]; int q = 1; while (q <= n) { jiazhi[q] = sc.nextInt(); zhongliang[q] = sc.nextInt(); q++; } int arr[][] = new int[n + 1][w + 1]; for (int i = 1; i < arr.length; i++) { for (int j = 1; j < arr[i].length; j++) { if (i == 1) { arr[i][j] = (j / zhongliang[i]) * jiazhi[i]; } else { if (j >= zhongliang[i]) { int one = arr[i - 1][j]; int two = arr[i][j - zhongliang[i]] + jiazhi[i]; arr[i][j] = one > two ? one : two; } else { arr[i][j] = arr[i - 1][j]; } } } } v = arr[n][w]; System.out.print(v); } }
0-1背包:
n\v 1 2 3 4 5
1 0 3 3 3 3
2 0 3 5 5 5
3 0 3 5 7 8
import java.util.*; public class 背包0_1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();// 物品总量 int m = sc.nextInt();// 重量至高值 int arr[][] = new int[n + 1][m + 1]; int w[] = new int[n + 1]; int v[] = new int[n + 1]; int q = 1; while (q <= n) { w[q] = sc.nextInt(); v[q] = sc.nextInt(); q++; } for (int i = 1; i < arr.length; i++) { for (int j = 1; j < arr[i].length; j++) { if (i == 1) { arr[i][j] = (j >= w[i]) ? v[i] : 0; } else { if (j >= w[i]) { int one = arr[i - 1][j]; int two = arr[i-1][j - w[i]] + v[i]; arr[i][j] = one > two ? one : two; } else { arr[i][j] = arr[i - 1][j]; } } } } int vl = arr[n][m]; System.out.print(vl); } }
0.0分
2 人评分