当前位置:首页 » 《随便一记》 » 正文

背包问题(0/1背包问题)(一维数组回滚解法和二维数组解法)_m0_57921272的博客

16 人参与  2022年04月18日 10:35  分类 : 《随便一记》  评论

点击全文阅读


                   

 1.(0,1)背包问题普通版(定义二维数组)采用动态规划

System.out.println("请输入背包容量和数量");
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt(); // 容量
int q=scanner.nextInt();  ///数量
int arr[]=new int[q+1];//存储重量
int brr[]=new int[q+1];//存储金额
arr[0]=0;
brr[0]=0;
int temp=1;
while(temp<=q){
    int c=scanner.nextInt(); // 重量
    int d=scanner.nextInt();  ///金额
    arr[temp]=c;
    brr[temp]=d;
    temp++;
}
int[][] max=new int[q+1][n+1];
for(int i=0;i<max.length;i++){
    for(int j=0;j<max[i].length;j++) {
        if (i == 0 || j == 0) {//初始化当容量为空或者物品为空最大金额为0
            max[i][j] = 0;
        } else {
            if (arr[i] > j) { //不能拿当前数值
                max[i][j] = max[i - 1][j];
            } else {
                //当可以拿时分为拿和不拿(取最大值)
                max[i][j] = Math.max((max[i - 1][j - arr[i]]) + brr[i], max[i - 1][j]);
            }
        }
    }
}
return max[q][n];

 2.(0,1)背包问题进化版(定义一维数组回滚)采用动态规划

                

System.out.println("请输入背包容量和数量");
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt(); // 容量
int q=scanner.nextInt();  ///数量
int arr[]=new int[q+1];//存储重量
int brr[]=new int[q+1];//存储金额
arr[0]=0;
brr[0]=0;
int temp=1;
while(temp<=q){
    int c=scanner.nextInt(); // 重量
    int d=scanner.nextInt();  ///金额
    arr[temp]=c;
    brr[temp]=d;
    temp++;
}
int[] max=new int[n+1];
for(int i=0;i<q+1;i++){
    //因为要用到上一列数组,所以要从后往前推防止覆盖
    for(int j=n;j>0;j--) {
        if (i == 0 || j == 0) {
            max[j] = 0;
        } else {
            if (arr[i] > j) { //不能拿当前数值
                max[j] = max[j];
            } else {
                //当可以拿时分为拿和不拿
                max[j] = Math.max((max[j - arr[i]]) + brr[i], max[j]);
            }
        }
    }
}
return max[n];

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/38314.html

容量  背包  数组  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • [糙汉嘴软心硬,娇妻日日晚起]小说精彩节选免费试读_「黎夏顾卫城」主线最终章倒计时
  • 我的亲妹妹我当做畜生,只有儿子来救我反转剧情试读片段_[***小宝李小翠]精彩章节免费试读
  • 往梦难复温,沈淮霆宋思予在线_往梦难复温,沈淮霆宋思予在线
  • 爱意清浅随风离(简凝夕陆靳燃),爱意清浅随风离
  • 「冲喜而已,侯爷别太爱」小说免费在线阅读_侯府侯爷乐瑶主线最终章倒计时
  • 好看的往梦难复温沈淮霆宋思予_往梦难复温沈淮霆宋思予
  • 天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局(秦意宋笙)全书秦意宋笙结局_秦意宋笙+结局列表_笔趣阁(天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局)
  • (番外)+(全书)往梦难复温(沈淮霆宋思予+番外+全书)_(往梦难复温+番外+全书)免费_笔趣阁(沈淮霆宋思予)
  • 江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)列表_江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)结局篇+番外在线
  • 池雾陆砚寒结局+番外(陆砚寒池雾)列表_池雾陆砚寒结局+番外(陆砚寒池雾)池雾陆砚寒结局+番外在线
  • 沈静怡傅励行+后续+结局(傅励行沈静怡)列表_沈静怡傅励行+后续+结局(傅励行沈静怡)沈静怡傅励行+后续+结局在线
  • 非典时,我被妻子的白月光误诊遗弃在病房节选角色羁绊特辑‌_田越苏雅白月光角色专属支线试读入口

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1