Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

What is a multiple knapsack in dynamic programming

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.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report