# 0-1背包问题（JAVA版）

## 一、0-1背包问题基础

``````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，符合最佳解决方案。
``````

## 二、质数拆分

``````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;
}
}
``````