[数据结构与算法]0-1背包问题（JAVA版）

一、0-1背包问题基础

把 i 件物品放入到容量为 v 的背包里面，我们需要找到最大能放入的情况，下图里面绿色圆圈代表价值为100，所占背包容量为20，其他几个同理。所以我们的最佳方案是放入价值高并且所占空间小的物品，也就是性价比高的物品。

对于每一个物品，我们都可以选择放或者不放，所以就有下面的情况：

我们只需要找到最大的那种情况就可以了，实现的代码如下：

public class Main {
	private static int[] weights = {20,40,80,10};
	private static int[] values = {100,60,200,40};
	public static int dp(int a, int n, int[] weights, int[] values) {
		int[][] map = new int[a+1][n+1];
		for(int i = 1; i <= n; i++) {
			int value = values[i-1];
			int weight = weights[i-1];
			for(int j = 1; j <= a; j++) {
				if(j < weight) {
					map[j][i] = map[j][i-1];
					continue;
				}
				map[j][i] = Math.max(map[j][i-1],map[j-weight][i-1]+value);
			}
		}
		return map[a][n];
	}
	public static void main(String[] args){
		System.out.println(dp(100,4,weights,values));
	}
}
//运行结果为300，符合最佳解决方案。

二、质数拆分

将 2019拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017 + 2 = 2019 视为同一种方法。

public class Main {
public static void main(String[] args) {
    int[] arr = new int[2500];
    int n = 0;
    for(int i=2;i<=2019;i++) {
        if(zhishu(i)) {
            arr[n++] = i;
        }
    }
    //map[i][j]含义：前i个数能刚好拼出数值为j的方式
    long[][] map = new long[n + 1][2019 + 1];
    for (int i = 0; i <=n; i++) {
        map[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 2019; j++) {
            if (arr[i - 1] > j) {
                map[i][j] = map[i - 1][j];
            } else {
                map[i][j] = map[i - 1][j] + map[i - 1][j - arr[i - 1]];
            }
        }
    }
    System.out.println(map[n][2019]);
}
public static boolean zhishu(int a) {
	for(int j=2;j<=Math.sqrt(a);j++) {
        if(a%j==0) {
            return false;
        }
    }
    return true;
}
}