动态规划
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的
应用场景
适用动态规划的问题必须满足最优化原理、无后效性和重叠性
实例
背包问题
前面提到贪心算法不能解决0-1背包问题,我们可以使用动态规划解决
问题描述:0-1
背包问题,将重量为(w1,w2,w3,w4,w5...)
、价值为(v1,v2,v3,v4,v5...)
的物品放入容量为N的背包中,怎样放价值最大
思路:
设v[i][j]
为放入前i
个物品到容量为j
的背包中的最大值,i
一定是小于物品总个数的,j
一定是小于N
的
则有等式:
v[0][j] = v[j][0] = 0
if (w[i] > j) { v[i][j] = v[i-1][j] }
if (w[i] <= j) { v[i][j] = Max(v[i-1][j], v[i-1][j-w[i]] + value[i]) }
public class PackageProblem {
public int maxVaule(int[] weight, int[] value, int capacity) {
int wl = weight.length;
int vl = capacity + 1;
int maxValue = 0;
int[][] v = new int[wl][vl];
for (int i = 0; i < wl; i++) {
for (int j = 0; j < vl; j++) {
if (i == 0) {
v[i][j] = 0;
} else if (j == 0) {
v[i][j] = 0;
} else {
if (weight[i] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = Math.max(v[i - 1][j],
v[i - 1][j - weight[i]] + value[i]);
}
maxValue = v[i][j];
}
}
}
print(v);
return maxValue;
}
private void print(int[][] numbers) {
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers[0].length; j++) {
System.out.printf("%d\t", numbers[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
PackageProblem packageProblem = new PackageProblem();
int[] weight = new int[]{7, 3 ,4, 5};
int[] value = new int[]{42, 12, 40, 25};
int capacity = 10;
int result = packageProblem.maxVaule(weight, value, capacity);
System.out.println(result);
}
}
网友评论