In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-21 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >
Share
Shulou(Shulou.com)06/03 Report--
This article mainly explains "what is a multiple knapsack in dynamic programming". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "what is a multiple backpack in dynamic planning"?
Multiple backpack
There are N items and a backpack with a capacity of V. The first item has a maximum of Mi pieces available. The space consumed for each item is Ci and the value is Wi. Find out which items can be loaded into the backpack so that the sum of the space consumed by these items does not exceed the capacity of the backpack, and the total value is the largest.
Multiple backpacks are very similar to 01 backpacks, why are they like 01 backpacks?
There are at most Mi pieces available for each item. Spreading out the Mi pieces is actually a 01 knapsack problem.
For example:
The maximum weight of the backpack is 10.
The items are:
Weight value quantity article 01152 article 13203 item 24302
What is the maximum value of items that can be carried in a backpack?
Is it different from the following?
Weight value quantity article 01151 article 01151 article 13201 article 24301 article 24301
No difference, this turns into a 01 knapsack problem, and each item is only used once.
The code to implement multiple backpacks in this way is as follows:
Void test_multi_pack () {vector weight = {1,3,4}; vector value = {15,20,30}; vector nums = {2,3,2}; int bagWeight = 10; for (int I = 0; I)
< nums.size(); i++) { while (nums[i] >1) {/ / nums [I] is reserved to 1, and other items are expanded weight.push_back (weight [I]); value.push_back (value [I]); nums [I] -;}} vector dp (bagWeight + 1,0); for (int I = 0; I)
< weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight [I]; jmurt -) {/ / ergodic knapsack capacity dp [j] = max (dp [j], dp [j-weight [I]] + value [I]);} for (int j = 0; j)
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 235
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.