概述

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;
}