背包入门 - AdaMeta730 - 博客园
Monday, August 24, 2020
9:34 PM
layout: post
title: 背包入门
categories: [背包, 模板题]
description: 背包入门
keywords: 背包, 模板#
背包
01背包#
给定NN个物品和容量是VV的背包，以及N个物体的vivi和wiwi，每个物体只有一件。
挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？
模板：01背包
朴素写法#
复制代码Copy
//#define judge
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];
int w[maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = V; j <= 0; j—) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][V];
return 0;
}
滚动数组优化空间#
复制代码Copy
define judge
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];
int w[maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
/
for (int i = 1; i <= n; i++) {
for (int j = V; j <= 0; j—) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
/
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j—) f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V];
return 0;
}
完全背包#
给定NN个物品和容量是VV的背包，以及N个物体的vivi和wiwi。每个物体有无限多件。
挑选一些物体，使得总体积小于等于VV，目标是使得总价值最大，问最大价值是多少？
朴素写法#
暴力做法：
复制代码Copy
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j—) {
f[i][j] = f[i - 1][j];
for (int k = 0; k v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] k] + w[i] k);
}
时间优化[*#](https://www.cnblogs.com/adameta/p/12370224.html#149360112)
在枚举kk时做时间优化：
因为在对k进行枚举时有：
f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,…,f[i−1][j−kv]+kw)f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,…,f[i−1][j−kv]+kw)
1:f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,…,f[i−1][j−kv]+kw)1:f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,…,f[i−1][j−kv]+kw)
2:f[i][j−v]=max(f[i−1][j−v],f[i−1][j−2v]+w,f[i−1][j−kv]+(k−1)w)2:f[i][j−v]=max(f[i−1][j−v],f[i−1][j−2v]+w,f[i−1][j−kv]+(k−1)w)
式子2中每一项都和式子1中从第二项开始的每一项相差1个w,那么就有:
完全背包的方程被优化为：f[i][j]=max(f[i][j−v]+w,f[i−1][j])f[i][j]=max(f[i][j−v]+w,f[i−1][j])
尤其注意以下细节：
复制代码Copy
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){//正确
// for(int j=V;j>= v[i];j—){//错误
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
复制代码Copy
define judge
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
//——————————————————————————————————————————
/时间优化->优化枚举k,因为
1. f[i][j] =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2_v]+2_w,…,f[i-1][j-k_v]+k_w);
2. f[i][j-v] =max( f[i-1][j-v], f[i-1][j-2_v]+_w,…,f[i-1][j-k_v]+(k-1)_w);
综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i
/
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){
// for(int j=V;j>= v[i];j—){
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
//滚动数组优化
cout << f[n][V];
return 0;
}
空间优化#
对于上述的方程：f[i][j]=max(f[i][j−v]+w,f[i−1][j])f[i][j]=max(f[i][j−v]+w,f[i−1][j])
观察方程f[i][j]f[i][j]可能是由f[i][j−v[i]]f[i][j−v[i]]转移过来，并且之前的状态一定是在上一行的前面位置。
因此，可以得知j−vj−v一定是在前面的数字情况，因此优化为1维的时候，前面的情况一定是上一个维度的。
优化空间的步骤,将阶段那一维度删除：即将i删除。
随后对
代码如下：
复制代码Copy
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <=V; j++){
f[j]=max(f[j-v[i]]+w[i],f[j]);
}
整合：#
复制代码Copy
// Author: oceanlvr
include
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
// int f[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
//朴素的完全背包
/
for (int i = 1; i <= n; i++)
for (int j = V; j >= 0; j—) {
f[i][j] = f[i - 1][j];
for (int k = 0; k v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] k] + w[i] k);
}
/
//——————————————————————————————————————————
/时间优化->优化枚举k,因为
1. f[i][j] =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2_v]+2_w,…,f[i-1][j-k_v]+k_w);
2. f[i][j-v] =max( f[i-1][j-v], f[i-1][j-2_v]+_w,…,f[i-1][j-k_v]+(k-1)_w);
综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i
/
/
for (int i = 1; i <= n; i++)
for (int j = 0; j <=V; j++){
// for(int j=V;j>= v[i];j—){
//错误的写法，因为f[i][j-v]在f[i][j]前面
//因此必须等f[i][j-v]更新之后才能更新f[i][j]
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);
}
/
//滚动数组优化
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <=V; j++){
f[j]=max(f[j-v[i]]+w[i],f[j]);
}
// cout << f[n][V];
cout << f[V];
return 0;
}
多重背包#
给定NN个物品和容量是VV的背包，以及N个物体的vivi和wiwi。每个物体有sisi件。
挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？
朴素写法[*#](https://www.cnblogs.com/adameta/p/12370224.html#3643340591)
暴力做法O(n2)O(n2)
暴力多重背包
复制代码Copy
define judge
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
int s[maxn], v[maxn], w[maxn];
int f[maxn][maxn];
int main() {
ifndef judge
freopen(“E:/yxc/in.txt”, “r”, stdin);
freopen(“E:/yxc/out.txt”, “w”, stdout);
endif
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> s[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k <= s[i]; k++) {
if (j >= k v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - k v[i]] + k w[i]);
}
}
}
}
cout << f[n][V] << endl;
return 0;
}
优化时间[*#](https://www.cnblogs.com/adameta/p/12370224.html#1634765249)
时间优化：
思路1：单调队列优化多重背包 背包问题 (附单调队列优化多重背包)
思路2：倍增的思想，把多重背包转为01背包，使用二进制对s[i]s[i]里面的数字范围打包：
用倍增的思想对同一物体进行打包之后物体的数目从SS变为了lgSlgS。因此时间复杂度由原来的O(NSV)O(NSV)变为O(NVlgV)O(NVlgV)。
建议看下『算法竞赛进阶指南』这本书上讲解倍增思想的部分。
复制代码Copy
//#define judge
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 2e4 + 5e3 + 10;
const int maxm = 2e3 + 10;
int v[maxn], w[maxn];
int f[maxn];
int main() {
cin >> n >> V;
int cnt = 0; //打包后的物体的编号
for (int i = 1; i <= n; i++) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
/倍增的思想多多重背包打包，转为01背包/
while (k <= s) {
cnt++;
//将这k个物体打包成一个物体，编号为cnt
v[cnt] = a k;
w[cnt] = b k;
s -= k;
k <<= 1; //倍增
}
if (s) {
//此时还剩下没有够2^{k+1}个的单位
//单独补上为一个物体
cnt++;
v[cnt] = a s;
w[cnt] = b s;
}
}
n = cnt; //更新为01背包的大小
//打包之后的多重背包转化为01背包
//此时直接做01背包相同的操作即可
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j—) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}
分组背包问题#
将物品分为NN组，每个组有若干个物体，给定若干物体的价值wiwi。每组只能选一个物体（组内是互斥的）。
问有背包的价值最大是多少？
分组背包问题
朴素写法#
复制代码Copy
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
int f[maxn][maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
//朴素写法
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= v[i][0]; k++) {
f[i][j] = max(f[i][j], f[i - 1][j]);
if (j - v[i][k] >= 0)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][V] << endl;
空间优化#
滚动数组空间优化：
对于分组背包的空间优化意义不太大，因为本身存储vv和ww就已经是二维的空间花销了。
复制代码Copy
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
//空间优化
for (int i = 1; i <= n; i++) {
for (int j = V; j >= 0; j—) {
for (int k = 0; k <= v[i][0]; k++) {
if (j - v[i][k] >= 0)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[V] << endl;
综合#
复制代码Copy
// Author: oceanlvr
include
using namespace std;
int n, V;
const int maxn = 1e2 + 10;
//第i组的第j个物品的体积和价值
int v[maxn][maxn];
int w[maxn][maxn];
// int f[maxn][maxn];
int f[maxn];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
v[i][0] = nn; //记录数量
for (int j = 1; j <= nn; j++) {
cin >> v[i][j] >> w[i][j];
}
}
/朴素写法
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= v[i][0]; k++) {
f[i][j] = max(f[i][j], f[i - 1][j]);
if (j - v[i][k] >= 0)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
/
//空间优化
for (int i = 1; i <= n; i++) {
for (int j = V; j >= 0; j—) {
for (int k = 0; k <= v[i][0]; k++) {
if (j - v[i][k] >= 0)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[V] << endl;
return 0;
}
已使用 Microsoft OneNote 2016 创建。
若有收获，就点个赞吧
0 人点赞
