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 + " ");
            }
        }
    }
全部评论
就一道完全背包吗 还是其他的题没什么必要说
1 回复 分享
发布于 2024-04-16 11:59 黑龙江
这个英雄是可以多次购买吗
点赞 回复 分享
发布于 2024-05-13 13:24 湖南

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
4
23
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务