当前位置:网站首页>为什么完全背包要用顺序遍历?简要解释一下
为什么完全背包要用顺序遍历?简要解释一下
2022-07-06 16:16:00 【童 话】
完全背包的意思是每种物品可以多次放入背包。
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]表示容量为j的背包装了物品后的最大价值。
1表示第i种物品的重量,2表示第i种物品的价值。
初始的dp[5]和dp[6]全为0。
这里,因为初始dp[6]是0,所以肯定选了dp[6 - 1] + 2,也就是肯定放入了第i种物品。
而dp[6]=……的执行要用到dp[5]的结果。
由于是顺序执行,所以dp[6]执行之前肯定已经执行了dp[5]=……。
dp[5]=……执行时,因为初始dp[5]是0,所以肯定选了dp[5 - 1] + 2,也就是肯定也放入了第i种物品。
所以说第i种物品放入了多次。
所以完全背包应该用顺序遍历。
边栏推荐
- 谁说新消费品牌大溃败?背后有人赢麻了
- Daily question brushing record (XV)
- What does front-end processor mean? What is the main function? What is the difference with fortress machine?
- js對JSON數組的增删改查
- 【通信】两层无线 Femtocell 网络上行链路中的最优功率分配附matlab代码
- 资产安全问题或制约加密行业发展 风控+合规成为平台破局关键
- Local deployment Zeppelin 0.10.1
- [unmanned aerial vehicle] multi unmanned cooperative task allocation program platform, including Matlab code
- Microsoft win11 is still "unsatisfactory". Multi user feedback will cause frequent MSI crashes
- 每人每年最高500万经费!选人不选项目,专注基础科研,科学家主导腾讯出资的「新基石」启动申报...
猜你喜欢
The programmer refused the offer because of low salary, HR became angry and netizens exploded
Basic chart interpretation of "Oriental selection" hot out of circle data
Gradle知识概括
零代码高回报,如何用40套模板,能满足工作中95%的报表需求
Newsletter L Huobi ventures is in-depth contact with genesis public chain
不要再说微服务可以解决一切问题了
今日睡眠质量记录78分
浅谈现在的弊端与未来的发展
Daily question brushing record (XV)
koa2对Json数组增删改查
随机推荐
Coscon'22 community convening order is coming! Open the world, invite all communities to embrace open source and open a new world~
Local deployment Zeppelin 0.10.1
Entropy information entropy cross entropy
Computer reinstallation system teaching, one click fool operation, 80% of people have learned
The same job has two sources, and the same link has different database accounts. Why is the database list found in the second link the first account
leetcode:236. The nearest common ancestor of binary tree
Microsoft win11 is still "unsatisfactory". Multi user feedback will cause frequent MSI crashes
What does security capability mean? What are the protection capabilities of different levels of ISO?
Wasserstein slim gain with gradient poverty (wsgain-gp) introduction and code implementation -- missing data filling based on generated countermeasure network
B站大佬用我的世界搞出卷積神經網絡,LeCun轉發!爆肝6個月,播放破百萬
ArrayExpress数据库里的细胞只有两个txt是不是只能根据Line到ENA下载测序跑矩阵?
The problem of ASP reading Oracle Database
传统企业要为 Web3 和去中心化做的 11 个准备
GPT-3当一作自己研究自己,已投稿,在线蹲一个同行评议
每日刷题记录 (十五)
[system analyst's road] Chapter 7 double disk system design (service-oriented development method)
Summary of three methods for MySQL to view table structure
js导入excel&导出excel
Gpt-3 is a peer review online when it has been submitted for its own research
每年 2000 亿投资进入芯片领域,「中国芯」创投正蓬勃