当前位置:网站首页>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 .
边栏推荐
- The "white paper on the panorama of the digital economy" has been released with great emphasis on the digitalization of insurance
- app通用功能測試用例
- Oracle EMCC 13.5 environment in docker every minute
- [automated testing framework] what you need to know about unittest
- okcc呼叫中心的订单管理时怎么样的
- iMeta | 华南农大陈程杰/夏瑞等发布TBtools构造Circos图的简单方法
- 专为决策树打造,新加坡国立大学&清华大学联合提出快速安全的联邦学习新系统
- GPIO簡介
- MATLIB从excel表中读取数据并画出函数图像
- Close unregistering application XXX with Eureka with status down after Eureka client starts
猜你喜欢

DAY THREE

Who said that new consumer brands collapsed? Someone behind me won

Design a red envelope grabbing system

How rider uses nuget package offline

I've been laid off, and I'll lose money for everything. The days when I once made a monthly salary of 20000 are not coming back

Server SMP, NUMA, MPP system learning notes.

DAY TWO

亚朵三顾 IPO

The programmer said, "I'm 36 years old, and I don't want to be rolled, let alone cut."
![Tourism Management System Based on jsp+servlet+mysql framework [source code + database + report]](/img/41/94488f4c7627a1dfcf80f170101347.png)
Tourism Management System Based on jsp+servlet+mysql framework [source code + database + report]
随机推荐
1000字精选 —— 接口测试基础
okcc呼叫中心的订单管理时怎么样的
leetcode:236. 二叉树的最近公共祖先
GPIO簡介
What is AVL tree?
DAY TWO
PDF文档签名指南
Introduction au GPIO
STM32 enters and wakes up the stop mode through the serial port
DAY FOUR
Yaduo Sangu IPO
DAY ONE
The programmer said, "I'm 36 years old, and I don't want to be rolled, let alone cut."
How does win11 restore the traditional right-click menu? Win11 right click to change back to traditional mode
Tourism Management System Based on jsp+servlet+mysql framework [source code + database + report]
Rider离线使用Nuget包的方法
DAY ONE
Common modification commands of Oracle for tables
Introduction to GPIO
Designed for decision tree, the National University of Singapore and Tsinghua University jointly proposed a fast and safe federal learning system