package others;
import java.util.Arrays;
/**
- 动态规划算法计算10个工人在5个金矿能获得的最大价值
- @author Administrator
*/
public class GetBestGold {
public static void main(String[] args) {
//工人10个
int w = 10;
//金矿开采所需的工人数量
int[] p = {5,5,3,4,3};
//金矿价值
int[] v ={400,500,200,300,350};
int maxVal = getMaxGoldV2(w,p,v);
System.out.println(maxVal);
}
private static int getMaxGoldV1(int w, int[] p, int[] v) {
//结果表f(n,w),
//n表示金矿的可选择范围，从1到5
//w表示工人数量
//result[i][j]表示，再有i个金矿可选的情况下，有j个工人能过获取的最大金矿值
int[][] resultTable = new int[v.length +1][w+1];
for(int i = 1; i <= v.length; i++){
for(int j = 1; j <= w; j++){
//如果人数不够采第i座金矿，只能获得前i-1座金矿的价值
if(j < p[i -1]){
resultTable[i][j] = resultTable[i-1][j];
}else{
//resultTable[i-1][j] 表示在有i -1做金矿可选的情况下，j个工人 如果不拿下第i-1座金矿能获得的价值
// resultTable[i-1][j - p[i-1]] + v[i-1] 表示在有i -1做金矿可选的情况下,如果拿下第i-1座金矿能获得的价值
resultTable[i][j] = Math.max(resultTable[i-1][j],
resultTable[i-1][j - p[i-1]] + v[i-1]);
}
}
}
return resultTable[v.length][w];
}
private static int getMaxGoldV2(int w, int[] p, int[] v) {
int[] results = new int[w+1];
//填充一维数组
for(int i = 1; i <= p.length; i++)
//如果是从左边开始，那么已经获得的金矿可以重新获得第二遍，最终永远只会获取性价比最高的
// for(int j = 1; j <= w;j++){
//如果从右边开始，默认就是先计算没有当前金矿的，然后加上当前金矿再比，不会获取多次
for(int j = w; j >= 1;j--){
if(j >= p[i-1]){
results[j] = Math.max(results[j],
results[j -p[i-1]] + v[i-1]);
}
}
System.out.println(Arrays.toString(results));
return results[w];
}
}
