思路
乍一看这是一个01背包的裸题。但是数据范围(10^5)是无法承受的。
但是发现(p_i)和(w_i)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。
二进制优化多重背包
多重背包是指限定物品数量的一种背包问题。
多重背包可以转化为01背包来解。也就是枚举当前这种物品选多少个。但是这种做法的复杂度是(O(NVS))S是背包内物品数量。
然后考虑优化上面的方法。因为每个数字都是可以用二进制来拼凑出来的。所以可以把每个物品的数量拆分成(2^x)这样就能拆分除(log)个物品。每个物品的价值都是(2^x imes w[i])的形式。体积都是(2^x imes p[i])的形式。
比如一种物品价值为3，体积为2，数量为13。那么这个物品可以拆分成以下物品：
[w:3 imes 1 p:2 imes 1 \
w:3 imes 2 p:2 imes 2 \
w:3 imes 4 p:2 imes 4 \
w:3 imes 6 p:2 imes 6 ]
注意最后一个6并不是(2^x)。
代码
/*
* @Author: wxyww
* @Date: 2019-01-20 09:01:19
* @Last Modified time: 2019-01-20 09:07:51
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int f[N],w[110],p[110],num[110],a[15][15];
int W,n,tot;
int main() {
n = read(),W = read();
int mx = 0,my = 0;
for(int i = 1;i <= n;++i) {
int x = read(),y = read();
a[x][y]++;
mx = max(mx,x);my = max(my,y);
}
for(int i = 1;i <= mx;++i) {
for(int j = 1;j <= my;++j) {
if(a[i][j]) {
++tot;
w[tot] = j;p[tot] = i;num[tot] = a[i][j];
}
}
}
for(int i = 1;i <= tot;++i) {
int k;
for(k = 1;num[i] - k >= k - 1;k <<= 1) {
for(int j = W;j >= p[i] * k;--j) {
f[j] = max(f[j],f[j - p[i] * k] + w[i] * k);
}
}
k = num[i] - k + 1;
for(int j = W;j >= p[i] * k;--j) {
f[j] = max(f[j],f[j - p[i] * k] + w[i] * k);
}
}
cout<<f[W];
return 0;
}