概述
01背包问题: 每件物品只能选一个
题解
i, v, max_w
2维
f[i,j]
状态表示
- 集合: 所有只考虑了前i个物品,其总体积不大于j的所有选法的集合
- 属性:Max
状态计算
- 集合分解
看第i个物品选或不选
时间复杂度
状态数量*每个状态所耗的时间 n^2 * 1
代码
1
//
// made by AugF
//
// 01背包 DP
// f[i,j] 所有用1~i物品且总体积为j的选法集合的权重的最大值
// 按照最后一个i是否选划分 f[i,j] = max( f[i-1,j], f[i-1,j-v[i]]+w[i])
// N*V*1 1e6 N
概述
每个物品选k个的二进制优化版本
题解
f[i,j]
状态表示
集合:所有只从前i个物品中选,且总体积不超过j的选法
属性:最大值
状态计算
集合划分
第i个物品最多选多少个
f[i,j] = max(f[i-1,j-kv]+kw) k=0,1,2,…,s[i]
二进制优化
f[i,j] = Max(f[i-1,j], f[i-1,j-v]+w,f[i-1,j-2v]+2w,…,f[i-1,j-sv]+sw)
f[i,j-v]=Max(f[i-1,j-v], f[i-1,j-2v]+w,…, f[i-1,j-(s+1)v]+(s+1)w)
二进制的优化方式
s=1023
1,2,4,8,…,512
0~1023
把多种背包某个物品有s次,转化为logS的物品的01背包问题,因此可以拼凑出问题的解
注意这里的凑数,最后一个是剩余的解
如 s=200
1,2,4,8,16,32,64,73
1~127
73~200
所以只凑出了0-200的解
s
1,2,4,8,..,2^k,c
c=s-(2^{k+1}-1)
c<2^{k+1}
s<=2^{k+2}-1;
优化步骤
总物品数:NlogS
时间:VNlogS
代码
#include<iostream>
using namespace std;
const int N=12010;
// N=1000*log2000=1000*12, 背包的个数
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s){
cnt++, v[cnt]=a*k, w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0) {
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
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;
}