文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java背包问题动态规划算法分析

2024-04-02 19:55

关注

背包问题

【题目描述】
一个旅行者有一个最多能装 MM 公斤的背包,现在有 nn 件物品,它们的重量分别是W1,W2,…,WnW1,W2,…,Wn,它们的价值分别为C1,C2,…,CnC1,C2,…,Cn,求旅行者能获得最大总价值。

【输入】
第一行:两个整数,MM(背包容量,M<=200M<=200)和NN(物品数量,N<=30N<=30);

第2…N+12…N+1行:每行二个整数Wi,CiWi,Ci,表示每个物品的重量和价值。

【输出】
仅一行,一个数,表示最大总价值。

【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12

我们可以通过自己打表的方式找变化求得状态方程
(横向表示容量,j)(纵向表示第几个,i)
#1 2 3 4 5 6 7 8 9 10
1 0 1 1 1 1 1 1 1 1 1
2 0 1 3 3 4 4 4 4 4 4
3 0 1 3 5 5 6 8 8 9 9
4 0 1 3 5 5 6 9 9 10 12

dp[i][j]----i表示物品个数,j表示容量,dp[i][j]的值表示在此状态的最大价值
由此我们可以写出状态转移方程:


if(j<w[i])//当容量小于重量,即不拿的情况下
	dp[i][j]=dp[i-1][j]//等于上一次的值
else
	 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

完整代码如下:


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m, n;
        int[] w = new int[35];
        int[] v = new int[35];
        m = in.nextInt();
        n = in.nextInt();
        int[][] dp = new int[35][205];//m容量,n数目个数

        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(j<w[i])
                {
                    dp[i][j]=dp[i-1][j];
                }else
                {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        //输出dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(dp[n][m]);
        in.close();
    }
}

当然,如果容量数字和物品个数很大的时候,这个表会很大,但是dp数组只与自己的上一次有关,会造成空间浪费,所以我们可以改进成滚动数组,减小空间,使其变成一维数组。

小tips:因为是滚动数组,所以如果第二层循环从1开始的话,可能会覆盖上一次的值,所以第二层循环的时候我们从后往前开始!


import java.util.*;
import java.lang.*;

public class Main {
    static int[]dp=new int[205];
    static int[] w = new int[35];
    static int[] v = new int[35];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m, n;
        m = in.nextInt();
        n = in.nextInt();
//        int[][] dp = new int[35][205];//m容量,n数目个数


        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if(j>=w[i])
                {
                    dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
                }
            }

        }
        //输出dp数组
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//        }
//        System.out.println(dp[n][m]);
        System.out.println(dp[m]);
        in.close();
    }
}

以上就是java动态规划算法之背包问题的详细内容,更多关于java动态规划背包的资料请关注编程网其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯