当前位置:网站首页>Why should a complete knapsack be traversed in sequence? Briefly explain
Why should a complete knapsack be traversed in sequence? Briefly explain
2022-07-07 00:00:00 【Fairy Tales】
Complete backpack means that each item can be put into the backpack many times .
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
dp[6] = max(dp[6], dp[6 - 1] + 2)
= max(dp[6], max(dp[5], dp[5 - 1] + 2) + 2)
dp[j] The capacity is j The maximum value of your backpack with items .
1 It means the first one i The weight of each item ,2 It means the first one i The value of an article .
Initial dp[5] and dp[6] All for 0.
here , Because initially dp[6] yes 0, So I must have chosen dp[6 - 1] + 2, That is to say, it must have been put into No i Items .
and dp[6]=…… The implementation of requires dp[5] Result .
Because it is executed sequentially , therefore dp[6] It must have been implemented before implementation dp[5]=…….
dp[5]=…… Execution time , Because initially dp[5] yes 0, So I must have chosen dp[5 - 1] + 2, That is to say, it must also be put into No i Items .
So the first i Items have been put in many times .
So the complete knapsack should be traversed in sequence .
边栏推荐
猜你喜欢
Why is bat still addicted to 996 when the four-day working system is being tried out in Britain?
Penetration test --- database security: detailed explanation of SQL injection into database principle
How to find out if the U disk file of the computer reinstallation system is hidden
氢创未来 产业加速 | 2022氢能专精特新创业大赛报名通道开启!
leetcode:236. 二叉树的最近公共祖先
Yaduo Sangu IPO
每年 2000 亿投资进入芯片领域,「中国芯」创投正蓬勃
GEO数据挖掘(三)使用DAVID数据库进行GO、KEGG富集分析
STM32通过串口进入和唤醒停止模式
The largest single investment in the history of Dachen was IPO today
随机推荐
iMeta | 华南农大陈程杰/夏瑞等发布TBtools构造Circos图的简单方法
Competition between public and private chains in data privacy and throughput
英国都在试行4天工作制了,为什么BAT还对996上瘾?
app通用功能測試用例
What is AVL tree?
The largest single investment in the history of Dachen was IPO today
Unity 颜色板|调色板|无级变色功能
Designed for decision tree, the National University of Singapore and Tsinghua University jointly proposed a fast and safe federal learning system
How to answer the dualistic opposition of Zhihu
谁说新消费品牌大溃败?背后有人赢麻了
TypeScript增量编译
【自动化测试框架】关于unittest你需要知道的事
Wasserstein Slim GAIN with Gradient Penalty(WSGAIN-GP)介绍及代码实现——基于生成对抗网络的缺失数据填补
[automated testing framework] what you need to know about unittest
【系统分析师之路】第七章 复盘系统设计(面向服务开发方法)
SuperSocket 1.6 创建一个简易的报文长度在头部的Socket服务器
Hydrogen future industry accelerates | the registration channel of 2022 hydrogen energy specialty special new entrepreneurship competition is opened!
Huawei mate8 battery price_ Huawei mate8 charges very slowly after replacing the battery
Local deployment Zeppelin 0.10.1
Matplotlib draws a histogram and adds values to the graph