4.15 虾皮笔试

用金币购买英雄联盟英雄的最大个数，要求给出具体方案。核心代码模式。其实就是背包问题求具体方案。

输入：[2,1,3,4,5],10

输出:[2,1,3,4]

//输入[2，1，3，5，4]，11

//输出2 1 3 5

public static void solution2(int[] weight, int bagsize){

int wlen = weight.length;

int value0 = 0;

int[] value = new int[wlen];//这里求的是最大个数，将价值都赋为个数1

Arrays.fill(value, 1);

//dp[i][j]表示背包容量为j时，从前i个物品能获得的最大价值

int[][] dp = new int[wlen+1][bagsize+1];

//背包容量j为0时，能获得的价值为0

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

dp[i][0] = value0;

}

// 从前0个物品中获取的价值只能为0

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

dp[0][j] = value0;

}

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

for (int j = 1; j <= bagsize; j++){

if (j < weight[i - 1]){//确保每一个状态都被覆盖

dp[i][j] = dp[i - 1][j];

}else{

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);

}

}

}

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

for(int j = 1;j<=bagsize;++j){

System.out.print(dp[i][j] + " ");

}

System.out.println("\n");

}

int[] item = new int[wlen + 1];// 下标i对应的物品若被选中，设置值为1

Arrays.fill(item, 0);// 将数组item的所有元素初始化为0

int j = bagsize;

for (int i = wlen; i > 0; i--) {

if (dp[i][j] > dp[i - 1][j]) {// 在最优解中，v[i][j]>v[i-1][j]说明选择了第i个商品

item[i] = 1;

j = j - weight[i-1];

}

}

System.out.print("包内物品的编号为：");

for (int i = 0; i < wlen + 1; i++) {

if (item[i] == 1) {

System.out.print(i + " ");

}

}

}

通用模板：

public static void solution2(int[] weight, int[] value, int bagsize){
        int wlen = weight.length;
        int value0 = 0;
        //dp[i][j]表示背包容量为j时，从前i个物品能获得的最大价值
        int[][] dp = new int[wlen+1][bagsize+1];
 
        //背包容量j为0时，能获得的价值为0
        for(int i = 0;i<=wlen;++i){
            dp[i][0] = value0;
        }
//        从前0个物品中获取的价值只能为0
        for(int j = 0;j<=bagsize;++j){
            dp[0][j] = value0;
        }

        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){//确保每一个状态都被覆盖
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }

//      用这段代码，dp[wlen+1][bagsize+1]是对的，但是中间过程状态
//        for(int i = 1;i<=wlen;++i){
//            for(int j = weight[i-1];j<=bagsize;++j){
//                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
//            }
//        }

        for(int i = 1;i<=wlen;++i){
            for(int j = 1;j<=bagsize;++j){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println("\n");
        }
        int[] item = new int[wlen + 1];// 下标i对应的物品若被选中，设置值为1
        Arrays.fill(item, 0);// 将数组item的所有元素初始化为0

        int j = bagsize;
        for (int i = wlen; i > 0; i--) {
            if (dp[i][j] > dp[i - 1][j]) {// 在最优解中，v[i][j]>v[i-1][j]说明选择了第i个商品
                item[i] = 1;
                j = j - weight[i-1];
            }
        }

        System.out.print("包内物品的编号为：");
        for (int i = 0; i < wlen + 1; i++) {
            if (item[i] == 1) {
                System.out.print(i + " ");
            }
        }
    }