動態規劃在求解背包問題中的應用

背包問題向來是動態規劃的典型問題，給定n個重量為w1,w2,...,wn，價值為v1,v2,...,vn的物品和一個稱重量為W的背包，求這些物品中最優價值的一個子集，且能夠裝到背包中。

之前用蠻力法做過背包問題蠻力法在求解最優解問題中的應用（JAVA）--旅行家問題、背包問題、分配問題

這篇文章中采用動態規劃思想解決，我們首先要推導出一個關系，用較小子實例的解來表示背包問題整體實例的解。我們先來考慮前i個物品（1<=i<=n）定義的實例，物品重量分別為w1,w2,...,wi，價值分別為v1,v2,...,vi，背包承重量為j（1<=j<=W）。設F(i, j)表示該實例的最優解的物品總價值，那么對于這樣一個實例，我們可以分為不取第i個物品和取第i個物品兩種情況，如果不取第i個物品，那么最優子集的價值為F(i-1, j)；如果取第i個物品，那么總價值為vi+前i-1個物品點1最大價值F(i-1, j-wi)。由此我們得出下面的遞推公式：

我們還可以知道初始條件：

當j>=0時，F(0, j) = 0； 當i >= 0時，F(i, 0) = 0

回溯解法：

import java.util.Scanner;public class Main {static int[] w = new int[10];static int[] v = new int[10];static int n, W;static Scanner in = new Scanner(System.in);public static void main(String[] args) {n = in.nextInt();W = in.nextInt();for (int i = 1; i <= n; i++) {w[i] = in.nextInt();v[i] = in.nextInt();}System.out.println(f(n, W));}private static int f(int n, int W) {if(n == 0 || W == 0){return 0;}for(int i = n;i >=0; i--) {if(w[i] > W) {return f(n-1, W);} else {return Math.max(f(n-1, W), f(n-1, W-w[i])+v[i]);}}return 0;} }

記憶化求解：

import java.util.Scanner;public class Main {static int[] w = new int[10];static int[] v = new int[10];static int[][] f = new int[10][10];static int n, W;static Scanner in = new Scanner(System.in);public static void main(String[] args) {n = in.nextInt();W = in.nextInt();for (int i = 0; i < f.length; i++) {for (int j = 0; j < f[0].length; j++) {f[i][j] = 0;}}for (int i = 1; i <= n; i++) {w[i] = in.nextInt();v[i] = in.nextInt();}System.out.println(f(n, W));}private static int f(int i, int j) {int temp;if(f[i][j] <= 0 && i>0) {if (j < w[i]) {temp = f(i-1, j);} else {temp = Math.max(f(i-1, j), v[i] + f(i-1, j - w[i]));}f[i][j] = temp;}return f[i][j];} }

由于DP問題經常有重疊子的計算問題，所以自頂向下的記憶化DP方法要優于自底向上的回溯算法。

滾動數組：

import java.util.Scanner;public class Main {static int maxV, maxM, n;static int[] v,k;static int[] f;public static void main(String[] args) {Scanner in = new Scanner(System.in);maxV = in.nextInt();maxM = in.nextInt();f = new int[maxV + 1];n = in.nextInt();v = new int[n + 1];k = new int[n + 1];for (int i = 1; i <= n; i++) {v[i] = in.nextInt();k[i] = in.nextInt();}for (int i = 1; i <= n; i++) {for (int j = maxV; j >= 0; j--) {for (int s = maxM; s >= 0; s--) {if (j >= v[i] ) {f[j] = Math.max(f[j-v[i]] + k[i], f[j]);}}}}System.out.println(f[maxV]);} }

總結

以上是生活随笔為你收集整理的动态规划在求解背包问题中的应用（JAVA）--回溯法、记忆化法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。