背包问题之动态归化算法

网上有一篇文章思路很清晰，http://www.sohu.com/a/149393500_479559，但图示的代码有些问题，自己的理解，把代码小改了下，贴出来大家一起学习。

public class Golden {

public static void main(String[] args) {

int[] g = { 40, 50, 90, 85, 42 };

int[] p = { 35, 45, 65, 54, 28 };

getMostGold(p.length, 88, g, p);

}

private static int getMostGold(int n, int w, int[] g, int p[]) {

int[] preResults = new int[w + 1];

int[] results = new int[w + 1];

// 填充边界格子的值

for (int i = 0; i <= w; i++) {

if (i < p[0]) {

preResults[i] = 0;

} else {

preResults[i] = g[0];

}

}

// 填充其余格子的值，外层循环是金矿数量，内层循环是工人数

for (int i = 1; i < n; i++) {

for (int j = 0; j <= w; j++) {

if (j < p[i]) {

results[j] = preResults[j];

} else {

results[j] = Math.max(preResults[j], preResults[j - p[i]] + g[i]);

}

}

preResults = results;

}

System.out.println(results[w]);

return results[w];

}

}