AcWing 7. 混合背包问题(分别选择三种背包问题的状态转移)
原题链接
中等
作者:
Jamyuan
,
2021-05-19 17:51:42
,
所有人可见
,
阅读 302
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int M = 1010;
int n, v, dp[M] = {0};
vector<int> base;
int main()
{
cin >> n >> v;
for(int i=0; i<n; i++)
{
int vi, wi, si;
cin >> vi >> wi >> si;
// 0/1背包
if(si == -1)
{
for(int j=v; j>=vi; j--)
dp[j] = max(dp[j], dp[j-vi] + wi);
}
// 完全背包
else if(si == 0)
{
for(int j=vi; j<=v; j++)
dp[j] = max(dp[j], dp[j-vi] + wi);
}
//多重背包II(二进制优化)
else
{
base.clear();
for(int i=1; si>0; i*=2)
{
if(si <= i)
{
base.push_back(si);
break;
}
base.push_back(i);
si -= i;
}
for(auto sibase:base)
{
for(int j=v; j>=sibase*vi; j--)
dp[j] = max(dp[j], dp[j-sibase*vi] + sibase * wi);
}
}
}
cout << dp[v];
return 0;
}