最大价值(多重背包)
解题思路
看到这道题,一眼就是背包问题,但是这个题目多了些条件
其实就是多重背包多了些条件,l和h就是确定了这个物品的数量
体积为0的物品预处理一下就行
AC code
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n,m;
int s[N],v[N],w[N]; //物品的数量,体积,价值
int f[N];
int main(){
cin >> n >> m >> v[0] >> w[0];
for(int i = 1;i <= m;i++){
int l,h;
cin >> l >> h >> v[i] >> w[i];
s[i] = l / h;
}
for(int i = v[0];i <= n;i++) f[i] = f[i - v[0]] + w[0]; //预处理体积为0的物品
//多重背包模板
for(int i = 1;i <= m;i++)
for(int j = n;j >= 0;j--)
for(int k = 1;k * v[i] <= j && k <= s[i];k++)
f[j] = max(f[j],f[j - k * v[i]] + k * w[i]);
cout << f[n] << endl;
return 0;
}
我哭死 我用完全 15/16
为什么可以先用完全背包处理然后再用多重背包处理,这是混合背包的思路吗?还是这道题目特殊可以这样写?
我的意思就是这一步预处理我没看懂,为什么可以直接先当作完全背包问题做一遍f
这个是不是混合背包问题里面的。。。。我没看
分组背包吧..每组只能选一个
每组不一定选一个
原来是多重背包,我的思路一直是完全背包加额外维护质量,没想到能直接算数量。
哈哈哈哈哈我第一反应也是完全背包