2019-11-04 回溯算法

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

}