多重背包问题(二进制倍增优化)_股市动态

多重背包问题(二进制倍增优化)

创始人

2025-05-28 22:32:30

0次

介绍

原题链接
多重背包问题就是给定每个物品的数量，那么多重背包的优化是利用二进制的倍增转换成了01背包问题。

首先讲解二进制倍增是个怎么回事

怎么说呢，举个例子吧，就是假如说这里有200个橘子，我们要选择n个橘子，那么暴力的做法就是一个一个的选直到选了n个橘子。
那我们用二进制优化是怎么做呢？
其实就是将这些橘子分成8堆，每堆是1、2、4…64, 73，从第一堆到第7堆是一个等比数列公比为2，最后一堆可能是2的倍数也可能不是。这些堆就能表示0到200的任意数，比如说1，2能表示0_{3**，然后再加上个4就能表示**4}7，算上0_{3**就能看出来1、2、4能表示**0}7的任何数。
那么怎么看能表示多大的数呢？
就是到了第m堆能表示的最大数是堆数x2-1 ，比如说到了堆数为4的堆，那么它能表示的最大的数为 4x2-1=7。
这一个最后不要128而要73呢？
其实就是到了128它能代表的最大数为255，已经超过了200了，而我们选到了64能表示的最大数为127，那么我们只要加上73表示的最大数就是200了。

然后就是如何转换成01背包的问题了

其实关键的就是预处理的这段代码，就是分成了好多堆，然后就是选不选这个堆，这就是个01背包问题了。
朴素版的多重背包就是从0开始遍历物品的数量，这里我们是选择1、2、4的数量分成堆，然后把堆赋予属性–体积和价值，物品1分成若干堆了，然后就将下一个物品再分成若干堆…。

需要注意的点

预处理的时候
预处理的时候注意不要少了 s -= k 还有就是 if(s > 0) 这个如果成立代表的就是最后一堆不是前一堆的二倍了。
遍历的时候
遍历的时候注意i的最大范围是堆的数量，也就是cnt的个数。

源码

#include using namespace std;const int N = 12010, M = 2010;int n, m;
int v[N], w[N];
int f[M];int main()
{cin >> n >> m;int cnt = 0;for (int i = 0; i < n; i ++ ){int a, b, s;cin >> a >> b >> s;int k = 1;while(k <= s){cnt ++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if (s > 0){cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}n = cnt;for (int i = 1; i <= n; i ++ ){for (int j = m; j >= v[i]; j -- ){f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【JavaEE】初识线程

下一篇：GPT-4震撼来袭，高级推理能力远超ChatGPT

多重背包问题(二进制倍增优化)

介绍

首先讲解二进制倍增是个怎么回事

然后就是如何转换成01背包的问题了

需要注意的点

源码

相关内容

热门资讯