背包

动态规划中的背包问题

01背包

有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。

分析： 考虑前i个物品，总体积为j时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j时的情况； 第i个物品取了，问题变成了考虑了前i −1个物品，总体积为j-v[i]时的情况；

状态：f[i][j]表示考虑了前i个物品，总体积为j时的最大收益。 转移：分别对应第i个物品没取f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])和取了两种情况。

错误写法

根据状态转移方程写出了这样的代码：

int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

在这个写法中，当j<=v[i]时，数组没有被更新，因此发生错误

正确写法

int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if(j<v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

滚动数组

但是当数据过大时，使用二维数组占用的空间太大，由于在计算i行时只用到了i-1行，所以可以用一个g数组存i-1行的数据，循环滚动f和g

int f[1010], g[1010];
int v[1010], w[1010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j >= v[i]) g[j] = max(f[j], f[j - v[i]] + w[i]);
            else g[j] = f[j];
        }
        memcpy(f, g, sizeof(g));
    }
    cout << f[m] << endl;
    return 0;
}

一维做法

状态：用f[i]表示总体积为i时的最大收益。 转移：f[j] = max(f[j], f[j - v[i]] + w[i])表示取前i个物品总体积为j时的最大情况

注意在枚举体积时，要从大向小枚举，若小到大枚举，则在枚举过程中可能会多次放入同一物品

int f[1010];
int v[1010], w[1010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

完全背包

有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，每种物品能用无限多次，问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。

完全背包的区别就是每个物品可以拿无数次

分析： 考虑前i个物品，总体积为j时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j时的情况； 第i个物品取了，问题变成了考虑了前i 个物品，总体积为j-v[i]时的情况；

状态：用f[i][j]表示考虑了前i个物品，总体积为j时的最大收益。 转移：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])分别对应第i个物品没取和取了两种情况。

普通做法：

int n, m;
int f[1010][1010];
int v[1010], w[1010];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

一维做法： 因为完全背包就是在01背包的基础上每个物品可以拿无数次，因此在枚举体积时正向枚举，即可在体积允许的情况下，将多个同一物品放入背包。

int f[1010];
int v[1010], w[1010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <=m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

延伸

如果要让背包里的物品体积正好是m，应该怎么做呢？

只需要把f数组初始化为负无限大，然后让f[0]=0，这样只有在体积刚好凑成的时候f才能数组才能被更新。

int f[1010];
int v[1010], w[1010];
int main() {
    int n, m;
    cin >> n >> m;
    memset(f, 128, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

多重背包

有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，可以用l[i]次。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。

分析：

第i种物品可以使用l[i] 次，我们可以把它拆成l[i]个物品，每个物品只能用一次； 然后就是个01背包问题啦!

int f[1010];
int v[1010], w[1010], l[1010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> l[i];
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= l[i]; k++) {
            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;
}

但是当数据过大时，这种做法会超时，可以采用二进制分组优化

二进制分组优化

从1,2,…,2m中选一些数字相加，可以得出任意[0,2m+1)内的值，每个数字只能用一次；

利用这条结论，我们可以用二进制表示体积m，例如：

5=1+4 6=2+4 7=1+2+4 8=1+1+2+4

因此对于第i种物品，可以使用l[i]次，那么可以把它拆成O(log n)个物品，每个物品只能用一次；

int f[2010];
int v[2010], w[2010], l[2010];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { 
		cin >> v[i] >> w[i] >> l[i];
	}
	for (int i = 1; i <= n; i++) {
		int res = l[i];
		for (int k = 1; k <= res; res -= k, k *= 2) {
			for (int j = m; j >= v[i] * k; j--) {
				f[j] = max(f[j], f[j - v[i]*k] + k*w[i]);
			}
		}
		for (int j = m; j >= v[i] * res; j--)
			f[j] = max(f[j], f[j - res * v[i]] + res * w[i]);
	}
	cout << f[m] << endl;
	return 0;
}

分组背包

有n种物品要放到一个袋子里，袋子的总容量为m。第i个物品属于第a[i]组，每组物品我们只能从中选择一个。第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。

分析： 把考虑了前i组物品以后，总体积为0，1，...，m时的最大收益都记下来； 考虑了前i组物品，总体积为j时分为两种情况： 第i组物品一个没取，问题变成了考虑了前 i−1组物品，总体积为j时的情况； 第i组物品取了，我们枚举取了其中的物品k，问题变成了考虑了前 i−1组物品，总体积为 j−v[k]时的情况； 状态：用f[i][j]表示考虑了前i组物品，总体积为j时的最大收益。 转移：f[i][j]= max (f[i-1][j], f[i-1][j-v[k]]+w[k])),其中c[i]表示第i组中物品的编号集合。

int n, m;
int f[1010][1010];
int v[1010], w[1010], a[1010];
vector<int>c[1010];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> v[i] >> w[i];
		c[a[i]].push_back(i);
	}
	for (int i = 1; i <= 1000; i++) {
		for (int j = 0; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			for (auto k : c[i]) {
				if (v[k] <= j)
					f[i][j] = max(f[i][j], f[i - 1][j - v[k]] + w[k]);
			}
		}
	}
	cout << f[1010][m] << endl;
	return 0;
}

一维做法

int n, m;
int f[1010];
int v[1010], w[1010], a[1010];
vector<int>c[1010];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> v[i] >> w[i];
		c[a[i]].push_back(i);
	}
	for (int i = 1; i <= 1000; i++) {
		for (int j = m; j; j--) {
			for (auto k : c[i]) {
				if (v[k] <= j)
					f[j] = max(f[j], f[j - v[k]] + w[k]);
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}

二维背包

有n种物品要放到一个袋子里，袋子的总容量为m，我们一共有k点体力值。第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，并且消耗我们t[i]点体力值，每种物品只能取一次。问如何选择物品，使得在物品的总体积不超过m并且花费总体力不超过k的情况下，获得最大的收益？请求出最大收益。

分析： 把考虑了前i个物品以后，总体积为0，1，...，m，总体力为0，1，...k时的最大收益都记下来； 考虑了前i个物品，总体积为j，总体力为x时分为两种情况： 第i个物品没取，问题变成了考虑了前 i−1个物品，总体积为j，总体力为x时的情况； 第i个物品取了，问题变成了考虑了前 i−1个物品，总体积为 j−v[i],总体力为x-t[i]时的情况； 状态：用f[i][j][x]表示考虑了前i个物品，总体积为j，总体力为x时的最大收益。 转移：f[i][j][x]=max(f[i−1][j][x],f[i−1][j−ν[i]][x−t[i]]+w[i])

这里就不贴普通做法的三维数组做法了，直接贴二维

int n, m, k;
int v[1001], w[1001], t[1001];
int f[1001][1001];
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i] >> t[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= v[i]; j--) {
			for (int x=k; x >= t[i]; x--) {
				f[j][x] = max(f[j][x], f[j - v[i]][x - t[i]] + w[i]);
			}
		}
	}
	cout << f[m][k] << endl;
	return 0;
}

单调队列

有n个生物，第i个生物会在第i到第a[i]天出现，它的攻击力为b[i]。其中对于所有i(1≤i<n)，满足a[i]≤a[i]+1。请输出每天出现的生物的攻击力的最大值。

分析： 假设现在考虑到了第i天，对于第 j(j<i)个生物，如果 b[j]<b[i],那么之后第j个生物都不用考虑了(在它存在期间，永远被第i个生物压制) ； 用一个队列，按编号从小到大的顺序，存放到目前为止，哪些生物是需要被考虑的(有可能在未来的某一天成为攻击力最高的生物) ；

int n, a[100010], b[100010], c[100010][2];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
	}
	int k = 0, l = 1;
	for (int i = 1; i <= n; i++) {
		for (; k >= l && b[i] >= c[k][0]; --k);//删掉队尾攻击力小的
		c[++k][0] = b[i]; c[k][1] = a[i];
		printf("%d\n", c[l][0]);
		for (; k >= l && c[l][1] == i; ++l);//删掉队头已经超过时限的元素
	}
    return 0;
}

//选择数字P
int head = 1, tail = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = q[head] + a[i];
        while (head <= tail && q[tail] >= dp[i]) tail--;
        q[++tail] = dp[i], p[tail] = i;
        while (head <= tail && p[head] < i - k) head++;
    }

多重背包

有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为v[i]，把它放进袋子里会获得w[i]的收益，可以用l[i]次。问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。

分析： 把考虑了前i种物品以后，总体积为0，1，…，m时的最大收益都记下来； 考虑了前i种物品，总体积为j时分为两种情况：

第i种物品没取，问题变成了考虑了前 i−1种物品，总体积为j时的情况；

第i种物品取了，枚举它取了k次，问题变成了考虑前 i−1 种物品，总体积为 j−v[i]×k时的情况；

状态：用f[i][j]表示考虑了前i种物品，总体积为j时的最大收益。

转移： f[i][j]=max(f[i−1][j],max f[i−1][j−v[i]×k]+w[i]×k)

把j按照 mod v[i]分类，只有同一类的状态间可以进行转移； 例如：当 v[i]=4时，其中一类为1，5，9，13，... 在某一类中下标为k的位置，可以转移到下标在 [k+1,k+l[i]]中的位置； 每个位置取最大值， 下标k，x之间转移的时候，(x−k)*w[i]怎么处理? 要求max(f[k]+(x−k)*w[i])，f[k]表示某一类中下标为k时的最值；因为x*w[i]对于每个位置是定值； 所以把 f[k]−k*w[i]放进单调队列就行啦！

int n, m, v, w, l,t, f[10001], c[10001][2];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> v >> w >> t;
		for (int j = 0; j < v; j++) {
			int k = 0, l = 1;//k是尾指针，l是头指针
			for (int pos = j, x = 1; pos <= m; pos += v, ++x) {
				int e = f[pos] - x * w, r = x + t;
				for (; k >= l && c[k][0] <= e; --k);
				c[++k][0] = e; c[k][1] = r;
				f[pos] = c[l][0] + x * w;
				for (; k >= l && c[l][1] == x; ++l);
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}