动态规划在求解背包问题中的应用（JAVA）--回溯法、记忆化法

动态规划在求解背包问题中的应用

背包问题向来是动态规划的典型问题，给定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]);
	}
}