多重背包问题
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
综合前面两个来看，相比于01背包是单纯的只有一个，完全背包是可以有无穷多个来看，多重背包就像是前面两种的综合。更加符合实际情况，不同体积与价值的物品有不同的数量。
于是，综合前面两个的dp表示以及dp转移方式，可以自然而然的想到可以在完全背包的时候，我们第一次所使用的三次循环的方式。因为这里的数据不是非常强。所以三次循环是不会TLE的。
最朴素的代码如下:
//极其朴素做法
#include
using namespace std ;
const int N = 110 ;
int f[N][N] ;
int w[N] , v[N] ,s[N];
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
cin >> v[i] >> w[i] >> s[i] ;
}
int i , j , k ;
for(i = 1 ; i <= n ; ++i)
{
for(j = 1 ; j <= m ; ++j )
{
f[i][j] = f[i-1][j] ;
for(k = 1 ; k <= s[i] && j >= k*v[i] ; ++k)
{
f[i][j] = max(f[i][j] , f[i-1][j-k*v[i]] + k * w[i]) ;
}
}
}
cout << f[n][m] << endl ;
return 0 ;
}
这种做法在这种强度的数据面前是可以过的，但是一旦数据到达了1000，这样的循环直接就GG了。
我们又来考虑一下，是否有可以将三次循环优化成两次的方法，唉，没错，我们又想到了完全背包问题的优化，他是根据递推公式进行优化的。
亦或者是根据有穷性的特性将多重背包问题转化成01背包问题，即为二进制优化。
先上代码。之后，我会解释二进制为什么可行？优化在什么地方？为什么会想到二进制来进行优化？是否还会有更好的优化方法？
二进制优化
#include
using namespace std ;
const int N = 10010 ;
int f[N] ;
int v[N] , w[N];
int main()
{
int n , m ;
int cnt = 0 ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
int a , b , c ;
cin >> a >> b >> c ;
int k = 1 ;
while(c >= k )
{
cnt ++ ;
v[cnt] = a * k ;
w[cnt] = b * k ;
c -= k ;
k *= 2 ;
}
if(c > 0)
{
cnt ++ ;
v[cnt] = a * c ;
w[cnt] = b * c ;
}
}
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 ;
return 0 ;
}
使用STL是这样的
#include
using namespace std ;
const int N = 10010 ;
vector < pair > vc ;
int f[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++i)
{
int a , b ,c ;
cin >> a >> b >> c ;
int k = 1 ;
while(c >= k )
{
vc.push_back({a*k , b*k}) ;
c -= k ;
k *= 2 ;
}
if(c > 0)
{
vc.push_back({c*a , c*b}) ;
}
}
for(auto num : vc)
{
for(int j = m; j >= num.first ;--j)
{
f[j] = max(f[j] , f[j-num.first]+num.second) ;
}
}
cout << f[m] << endl ;
return 0 ;
}
二进制优化的思路：
1.明确一个思想，例如一堆数字，1，2，4，8，16，32，64……可以用来表示1~128的任何一个数字。
所以对于多重背包问题，对于他的价值和体积来说，我们可以使用二进制将其拆解成一些子项。这样在朴素暴力的时候，我们是一个一个遍历的，但是二进制的时候，我们可以通过选取其中的一些值来达到之前需要选取多个同样体积与价值的累加的效果。
当然，你也可以直接将过程理解成这样一个故事(估计会方便理解一些)：
我们想要从我们以前做过的题目中寻求思路，但是我们只写过01背包呀。唉！！正好，这些也是正好是有穷个数的物品，我们完全可以将其拆成一个一个的，但是你会发现，不行哎，没卵用，因为它仍然是一个个的，同之前的暴力做法不是一样的吗？？？(我是sb)
于是，我就在百度上或者是google上搜索，将一个大数如何可以拆解成很多小数，同时可以表示一段范围内的任意一个实数，唉，这时候你突然看到了，可以用二进制进行优化。
2.将有限个固定体积与价值的东西通过二进制累加变成不同体积与价值但是数量为1的物品，就转变成了01背包问题，然后套用01背包的模板即可。
所以优化在什么地方呢？
从时间复杂度来看，朴素做法的时间复杂度为O(mns) 。经过二进制优化后为O(2mnlogs).
其实就是相当于本来有n个东西，你需要一个个来看，但是通过二进制优化，我们可以用lgn的东西来进行表示。其实对于代码来说，循环的次数是没有发生变化的，只是做选择的次数由n变成lgn了。
这时候，提一句，
对于dp来说，dp的时间复杂度可以简单理解为
dp的时间复杂度 == 问题的个数 * 问题选项的个数
对了，还可以用dequeue，也就是单调队列进行优化，过一段时间在更……….
