背包问题

ACwings的模板中，j从0开始枚举，如果之后出错可试试看

01背包

取或不取，一件物品最多用一次

状态表示

取或不取两种情况 其状态表示就是取了哪些

不同的取法构成集合，具体而言，是从1~i中的不同取法，满足不超过背包容量的条件的集合，要使取法的价值最大

状态计算

分为两类，取第i件和不取第i件

• 不取的计算可以看作从 1~i-1 里取，使得价值最大
• 取则可以看作是，先不取，在1~i-1中取不超过总重量-第i件重量的物品，再取第i件，使得价值最大

实现

抽象实现，有m的重量可以装，可以从0开始遍历所有的可能重量；有n个物品可以装，每一个情况都分为有没有第i个两种选择，用递推做

由于初始值，选0个时值是确定的，且重量从0开始增加，即当i+1时，i的所有值已经算出来了，所以可以递推

int v[N], w[N];
int f[N][N];
int main()
{
    int n, m;
    cin >> n >> m;
    
    //f[0][1~m] = 0  取0件
    //从取0件开始，用递推推出每种选择的结果
    //从头遍历找到最后答案
    
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];  // f[i][j]指这个值的最终结果，这一部先算，再考虑是这部分大还是另一个分类大
            if(v[i] <= j)  f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}

一维优化

思路是，将原本是二维的数组变成一维 依据：每次计算只会用到上组计算的值，而不会用到之前多组，这意味着可以覆盖着用上组的计算结果来求这组的计算结果，即转为一维

int f[N];//优化到一维
 
 
for(int i = 1; i <= n; i ++)
	//for(int j = 1; j <= m; j ++)  算到i的时候i-1已经被覆盖了
	/*如果第i件放不下，则计算结果和上一组没区别
	for(int j = m; j > 0; j --)
	{
		if(v[i] <= j)  f[j] = max(f[j], f[j - v[i]] + w[i]);
	}*/
	//逆过来算，防止被覆盖掉
	for(int j = m; j >= v[i]; j --)
		f[j] = max(f[j], f[j - v[i]] + w[i]);
	
cout << f[m] << endl;

这种方法称为 滚动数组

完全背包

取多少件都可以，只要不超重

状态表示

和01背包一致

状态计算

如何分类计算 分为：第i个选0~k的多种情况，计算最大值，计算方法一致，先去掉k个，再加上k个

实现

// 基本代码
for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            for(int k = 0; k * v[i] <= j; k ++)
            {
                // 因为k进来的条件保证了j>=vi
                //这里不再是i-1，是因为取不取第i件的情况都在循环里
                //因为还有k循环，语句只是在k去不同的值里找到最大值
                f[i][j] = max(f[i][j], f[i-1][j - k*v[i]] + k * w[i]);
            }

优化为两维

思路是： $f(i,j)=max(f(i-1,j),f(i,j-v)+w,f(i,j-2v)+2w\dots \dots f(i,j-kv)+kw)$ $f(i,j-v)=max(f(i-1,j-v),f(i,j-2v)+w\dots \dots f(i,j-(k-1)v)+(k-1)w)$ 发现上下两式差一个w（除上式第一项） 即可以化为 $f(i,j)=max(f(i-1,j),f(i,j-v)+w)$

for(int i = 1; i <= n; i ++)
	for(int j = 1; j <= m; j ++)
		/*这层去掉
		for(int k = 0; k * v[i] <= j; k ++)
		{
			f[i][j] = max(f[i][j], f[i-1][j - k*v[i]] + k * w[i]);
		}*/
		{
			f[i][j] = f[i - 1][j]; //如果判断没过，i拿不了，记录当前值为上一个的值
			if(v[i] <= j)  f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
		}

一维

和01背包一致，只是这次的优化里需要用到的数没有被提前覆盖掉，不用逆序

或者理解为最后在哪里取

for(int i = 1; i<= n; i ++)
	/*改
	for(inr j = 1; j <= m; j ++)
	{
		f[i][j] = f[i-1][j];
		if(v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
	}*/
	for(int j = v[i]; j <= m; j ++)
		//f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		//这里的计算不会与之前的计算冲突
		f[j] = max(f[j], f[j - v[i]] + w[i]);

多重背包

每件物品数量有上限，怎么选价值最大

状态表示

从1~i件物品中选的物品的组合，要找到最大价值的选择

状态计算

划分为第i件物品选 0、1、2 …… s（or 超重）件来计算

选0件，就是在 i - 1 中选；选其他的就是先选 i - 1 中不超过 总重量 j 减去 k 件第i件的重量的最大值再加上 k 件 i 件

朴素

 
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);  //如果第i件拿不了，那f[i][j] = f[i-1][j]
            }

二进制优化

将每个物品的上限分为二进制的数的组合 例如 上限 s = 1023 分为 1，2，4，8…… 512 就可以类似于二进制数将所有能表示的数分组表示出来

如果不是刚刚好可以分为2的倍数呢？将最后一个数设为 $s-2_{max}^k$，由于$2_{max}^k$之前的2的倍数可以组合成$(0,2^{k+1}-1)$范围内所有数，那这些数分别与$s-2_{max}^k$就可以组合成s以内的所有数了（这样会有一些数重复表示，但是已经是很大的优化了）

分组之后就是 01背包问题

//注意范围，将一个数分为二进制数后，分组数增加
const int N = 12000;
 
int v[N], w[N], f[N];
 
int main()
{
    int n, m;
    cin >> n >> m;
    
    int cnt = 0;
    for(int i = 0; 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;
        }
        //要是s还有
        if(s)
        {
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;  //更新n
    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;
}

分组背包

分组，每组最多选一个

状态表示

所有选法的集合里，要一个最大价值

状态计算

将第i组的选择分为不选第i组和选第i组中的第几个 不选：就是在1~i-1组中选的最大值 选：按每组的不同选择计算最大值，要求选了之后不超重

实现

int v[N][N], w[N][N], s[N];
int f[N];
 
int main()
{
    int n, m;
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }
    //直接化成 1 维，因为每次要用前面的数来计算（j - v[i][k])，所以 j 要倒着算才不会覆盖掉前面的数
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= 0; j --)
            for(int k = 1; k <= s[i]; k ++)
                if(v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                
    cout << f[m] << endl;
    
    return 0;
}