首页 > 其他分享 >完全背包理论基础

完全背包理论基础

时间:2023-08-12 18:01:44浏览次数:34  
标签:遍历 weight int 理论 bagWeight 完全 背包 dp


完全背包跟01背包的代码区别就是在第二层背包的遍历的时候是正序的!

先遍历物品还是背包是一样的

//先遍历物品,再遍历背包
private static void testCompletePack(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i < weight.length; i++){ // 遍历物品
        for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

//先遍历背包,再遍历物品
private static void testCompletePackAnotherWay(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
        for (int j = 0; j < weight.length; j++){ // 遍历物品
            if (i - weight[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}


标签:遍历,weight,int,理论,bagWeight,完全,背包,dp
From: https://blog.51cto.com/u_15806469/7060465

相关文章

  • CAP 理论
    CAP理论基本概念维基百科的翻译版本在理论计算机科学中,CAP定理(CAPtheorem),又被称作布鲁尔定理(Brewer’stheorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:一致性(Consistency):等同于所有节点访问同一份最新的数据副本;可用性(Availability):每次请求......
  • 代码随想录算法训练营第十六天| 104.二叉树的最大深度 111.二叉树的最小深度 222.
      104.二叉树的最大深度 (优先掌握递归)    卡哥建议:什么是深度,什么是高度,如何求深度,如何求高度,这里有关系到二叉树的遍历方式。大家要先看视频讲解,就知道以上我说的内容了,很多录友刷过这道题,但理解的还不够。   题目链接/文章讲解/视频讲解:https://programmerc......
  • 浅谈背包
    引入背包问题,是大多数oier在学习动态规划(下文用dp代替)的过程中,最先接触到的问题。它看似简单,有蕴含着无穷的变化。本文便对作者接触过的背包问题做一个总结。背包问题,一般情况下指:你有\(n\)个物品和一个容量为\(m\)的背包,每个物品有重量\(w\)和价值\(v\),各个物品间可......
  • 6529: 构造完全图 最小生成树
    描述 对于完全图G,若有且仅有一棵最小生成树为T,则称完全图G是树T的扩展出的。给你一棵树T,找出T能扩展出的边权和最小的完全图G。 输入 第一行N表示树T的点数。接下来N-1行:Si,Ti,Di;描述一条边(Si,Ti)权值为Di。保证输入数据构成一棵树。对于20%的数据,N<=10对于50%的......
  • 在不完全重合的情况下,判断线经过另一线段的方法
    importlogginglogging.basicConfig(level=logging.INFO,format='%(asctime)s-%(filename)s[line:%(lineno)d]-%(levelname)s:%(message)s',datefmt='%Y-%m-%d%H:%M:%S')importnumpyasnpfromshapely.......
  • 博弈论——完全信息静态博弈(二)
    完全信息静态博弈是指参与者在做出决策之前拥有所有可能的信息,包括对手的策略和利益。因此,每位参与者可以准确地评估各种选择对自己和对手的影响。这种情况下,决策的结果是确定性的,不受随机因素影响。参与者通过理性分析和预测对手的行为,以最大化自身利益。完全信息静态博弈广泛应......
  • 构造完全图
    题目描述对于完全图G ,若有且仅有一棵最小生成树T ,则称完全图G 是树T 扩展出的。给你一棵树T ,找出T 能扩展出的边权和最小的完全图G。输入格式第一行正整数N  表示树T 的点数;接下来N-1 行三个整数u,v,w ;描述一条边 (u,v) 权值为w;保证输入数据......
  • 【技术积累】Linux中的命令行【理论篇】【八】
    basename命令命令介绍在Linux中,basename命令用于从给定的路径中提取文件名或目录名。它的语法如下:basename[选项][路径]命令介绍选项:-s,--suffix=SUFFIX:指定要删除的后缀。-a,--multiple:处理多个路径参数。-z,--zero:以null字符作为分隔符。路径:要提取文件名或目录名的......
  • 【我和openGauss的故事】openGauss 主备架构及同步复制模式理论学习与验证测试
    【我和openGauss的故事】openGauss主备架构及同步复制模式理论学习与验证测试尚雷[openGauss](javascript:void(0);)2023-08-0818:00发表于四川收录于合集#第六届openGauss技术文章征集初审合格文章62个备注:非常感谢在这研究本文相关内容中openGauss数据库官网行尘(张旭博)......
  • 软件测试|深入解析Docker Run命令:创建和启动容器的完全指南
    简介Docker是一种流行的容器化平台,用于构建、分发和运行应用程序。其中一个最基本且重要的Docker命令是dockerrun,用于创建和启动容器。本文将详细解析dockerrun命令的用途、参数和示例,帮助您全面掌握创建和启动容器的过程。dockerrun在Docker中,容器是运行应用程序的独立环境。do......