背包九讲之——多重背包

多重背包

多重背包是限制了每种物品数量的完全背包，因此可以按照完全背包的思路来做（完全背包见上篇博客）。
dp[i][j]表示前i种物品在容量为j的情况下最大价值，那么就有ki+1种情况：
1.不选：dp[i][j]=dp[i-1][j];
2.选一件：dp[i][j]=dp[i-1][j-v[i]]+w[i];
3.选两件：dp[i][j]=dp[i-1][j-2v[i]]+2w[i];
…
ki+1.选ki件：dp[i][j]=dp[i-1][j-kiv[i]]+kiw[i];
->dp[i][j]=max{dp[i-1][j-kv[i]]+kw[i]};0<=k<=ki;
那就开始遍历吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=ki && k*v[i]<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[n][m];

显然这种做法是正确的，但是并不理想，复杂度太高O(nmk)，差不多为O(n3)的样子，我们继续进行优化。
考虑一种思想：将第i种物品分成ki个数量为1的物品，化成01背包，使用01背包的办法解答，这种想法当然是很好的，但是算来复杂度并无变化。那么我们就不能把ki分成ki个1，需要进行其他化法——二进制化简。其实质是二进制可以表示任何一个十进制整数，例如 11，我们化成：1 2 4 4，我们使用1 2 4 4这四个数随意组合，可以组合出0~11.其中前三个数是二进制依次分出，而第三个数应当分出8，但是不足，那么就取剩下的数。开分！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct love
{
int v,w;
};
int main()
{
dp[0]=0;
vector<love> wife;
for(int i=1;i<=n;i++)
{
for(int k=1;k<=ki;k*=2)//将ki二进制划分成log ki个物品
{
ki-=k;
wife.push_back({v[i]*k,w[i]*k});
}
if(ki)	wife.push_back({v[i]*ki,w[i]*ki});
}
//现在就已经转化为01背包问题（见前两篇博客）
for(auto it:wife)//也可用迭代器噢
{
for(int j=m;j>=it.v;j--)//01背包的从大往小遍历
{
dp[j]=max(dp[j],dp[j-it.v]+it.w);
}
}
cout<<dp[m];
}

我发的代码都是不完整的核心代码，补充好基本定义输入输出是可以直接使用的。
以上就是多重背包了，若有错误还望指出，另外多重背包还有单调队列的更好的优化方法，蒟蒻不会。。。各位dalao可以看看别人的博客，谢谢！

最后

以上就是健忘时光最近收集整理的关于背包九讲之——多重背包的全部内容，更多相关背包九讲之——多重背包内容请搜索靠谱客的其他文章。