首页 > 编程语言 >动态规划 01背包(算法)

动态规划 01背包(算法)

时间:2024-10-31 22:51:42浏览次数:3  
标签:01 容量 int ++ 算法 背包 物品 new

现有四个物品,小偷的背包容量为8,怎么可以偷得价值较多的物品

如:

物品编号: 1     2      3      4 

物品容量: 2     3      4      5

物品价值: 3     4      5      8

记f(k,w) ,当背包容量为w,可以偷k件物品,所能偷到的最大价值

以f(4,8)为列,记录每次偷取物品有两种情况 偷//不偷,如果偷取出物品的价值并减少对应背包的容量,如果不偷,则不需要取出价值,也不需要减去对应的容量, 依次找到偷取物品为0个,或者容量不够时为止。

由上述递推可得下面公式

 

 

 

代码实现:

 

package 算法;

public class 背包 {
    public static void main(String[] args) {
        int[][] f = new int[5][9];
        int[] w = new int[]{0, 2, 3, 4, 5};
        int[] v = new int[]{0, 3, 4, 5, 8};

        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < 9; j++) {
                if (w[i] > j) {
                    f[i][j] = f[i - 1][j];
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
                }
                }
         }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.println(i+" "+j+" "+f[i][j]);
            }
        }
        }
    }

标签:01,容量,int,++,算法,背包,物品,new
From: https://blog.csdn.net/2301_80419036/article/details/143418719

相关文章

  • [智能自动编曲软件 ]band in a box 2024 中文汉化完整版+安装方法 [WiN](201GB+)
    智能自动编曲软件2024有50多项新功能!其中包括许多重要的新功能。首先是新的音轨窗口。与大多数DAW音轨窗口类似,它显示所有音轨,允许在DAW用户熟悉的环境中对音轨进行无损数据操作。新的音轨窗口包括使用RealTracks内容创建循环和乐句的特定支持。现在,浮动窗口无处不......
  • [HCTF 2018]WarmUp
    题目链接:https://buuoj.cn/challenges#[HCTF2018]WarmUp打开环境后如下。查看页面源代码,发现存在提示"source.php"。<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"conte......
  • [极客大挑战 2019]Havefun
    链接:https://buuoj.cn/challenges#[极客大挑战2019]Havefun打开环境后如下所示。在BurpSuite中(或直接CTRL+U)查看源代码后,可以发现存在如下代码。$cat=$_GET['cat'];echo$cat;if($cat=='dog'){echo'Syc{cat_cat_cat_cat}';}尝试输入Payload:?cat=dog后即可......
  • [极客大挑战 2019]EasySQL
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]EasySQL。打开后,页面如下所示:可以看到,只有一个登录框,没有其他的内容,一般这种情况,应当先考虑SQL注入。在密码框中直接插入万能密码:'or1=1;#。成功获取flag。知其然,知其所以然。一些常见的登陆功能的后端实现......
  • 大模型算法面试题总结
    更多面试题总结,请移步至​https://i.afbcs.cn/naPbNY​1.什么是大型语言模型(LLMs)以及它们的工作原理是什么?大型语言模型(LLMs)是设计用来理解、处理和生成类似人类文本的高级人工智能系统。例子包括GPT(生成预训练变换器)、BERT(来自变换器的双向编码器表示)、Claude和Llama。这些......
  • 告别龟速加载:三种压缩算法让你的网站瞬间提速!
    三种压缩算法,让你的网站飞起来!!!2万字深度长文,让你一次看个爽!!!欢迎订阅专栏,永不收费,hacker精神,更快获得第一手优质博文!!!前言在当今快节奏的互联网世界,用户对网站加载速度的要求越来越高。一个加载缓慢的网站不仅会损害用户体验,还会影响搜索引擎排名,最终导致流量和转......
  • 【深度学习】从公式推导来深入理解误差反向传播算法2:《深度学习入门基于Python的理论
    《深度学习入门基于Python的理论与实现》中实现了2层全连接神经网络的代码对MNIST数据集的28x28像素0-9手写数字灰度图像进行分类,本文将重点对代码中的two_layer_net类的gradient函数中的误差反向传播的代码进行公式推导验证。验证小批量数据的交叉熵损失函数对第2层权重......
  • Python基于TensorFlow实现卷积神经网络-双向长短时记忆循环神经网络加注意力机制回归
    说明:这是一个机器学习实战项目(附带数据+代码+文档+视频讲解),如需数据+代码+文档+视频讲解可以直接到文章最后关注获取。1.项目背景随着大数据时代的到来,对复杂数据结构的理解和预测成为许多领域的重要课题。在这些领域中,无论是视频分析、语音识别还是自然语言处理,都面临着需......
  • 每日算法一练:剑指offer——数组篇(7)
    1.文物朝代确认        展览馆展出来自13个朝代的文物,每排展柜展出5个文物。某排文物的摆放情况记录于数组 places,其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中,编号为0的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否能够视为连......
  • AI预测福彩3D采取888=3策略+和值012路或胆码测试10月31日新模型预测第126弹
            经过100多期的测试,当然有很多彩友也一直在观察我每天发的预测结果,得到了一个非常有价值的信息,那就是9码定位的命中率非常高,100多期一共只错了12次,这给喜欢打私房菜的朋友提供了极高价值的预测结果~当然了,大部分菜友还是走的正常渠道,因此,得想办法进行缩水,尽可能......