当前位置:网站首页>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 .
边栏推荐
- 【CVPR 2022】目标检测SOTA:DINO: DETR with Improved DeNoising Anchor Boxes for End-to-End Object Detection
- app通用功能测试用例
- leetcode:236. 二叉树的最近公共祖先
- PostgreSQL使用Pgpool-II实现读写分离+负载均衡
- (leetcode) sum of two numbers
- 为什么完全背包要用顺序遍历?简要解释一下
- [system analyst's road] Chapter 7 double disk system design (service-oriented development method)
- Design a red envelope grabbing system
- openresty ngx_lua子请求
- Supersocket 1.6 creates a simple socket server with message length in the header
猜你喜欢
STM32 enters and wakes up the stop mode through the serial port
Introduction to GPIO
Cas d'essai fonctionnel universel de l'application
leetcode:236. The nearest common ancestor of binary tree
氢创未来 产业加速 | 2022氢能专精特新创业大赛报名通道开启!
【通信】两层无线 Femtocell 网络上行链路中的最优功率分配附matlab代码
基于SSM框架实现的房屋租赁管理系统
[automated testing framework] what you need to know about unittest
The intranet penetrates the zerotier extranet (mobile phone, computer, etc.) to access intranet devices (raspberry pie, NAS, computer, etc.)
MVC and MVVM
随机推荐
专为决策树打造,新加坡国立大学&清华大学联合提出快速安全的联邦学习新系统
Common modification commands of Oracle for tables
STM32通过串口进入和唤醒停止模式
app通用功能测试用例
Pdf document signature Guide
AVL树到底是什么?
Tourism Management System Based on jsp+servlet+mysql framework [source code + database + report]
每年 2000 亿投资进入芯片领域,「中国芯」创投正蓬勃
MIT 6.824 - Raft学生指南
Wasserstein Slim GAIN with Gradient Penalty(WSGAIN-GP)介绍及代码实现——基于生成对抗网络的缺失数据填补
【向量检索研究系列】产品介绍
Compile logisim
Introduction to GPIO
okcc呼叫中心的订单管理时怎么样的
(LeetCode)两数之和
Basic chart interpretation of "Oriental selection" hot out of circle data
Oracle EMCC 13.5 environment in docker every minute
Wechat applet UploadFile server, wechat applet wx Uploadfile[easy to understand]
A way of writing SQL, update when matching, or insert
陀螺仪的工作原理