背包问题
-
01背包
一共N个物品,背包容量V,每种物品只可以选
一次
,求背包容纳的最大价值
朴素版
f[i][j] = 从前i个物品中选,体积不超过j的所有选法中价值的最大值
状态转移方程:f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
int 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 = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m];
return 0;
}
优化版
优化思路:在朴素版中,第i
层只会用到i-1
层的数据,利用迭代的思想,是其变成一维数组滚动更新。
特别注意的是:f[j]
计算会用到第i-1
层的f[j]
和f[j - v[i]]
,若采用递增遍历,f[j - v[i]]
已经被更新成i
层的数了
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int n, m;
int 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 = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
return 0;
}
-
完全背包
一共N个物品,背包容量V,每种物品只可以选
无限次
,求背包容纳的最大价值
朴素版
f[i][j] = 从前i个物品中选,体积不超过j的所有选法中价值的最大值
状态转移方程:f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int 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 = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout << f[n][m];
return 0;
}
优化版
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int 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[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
return 0;
}
-
多重背包
一共N个物品,背包容量V,每种物品只可以选
有限次s[i]
,求背包容纳的最大价值
朴素版
f[i][j] = 从前i个物品中选,体积不超过j的所有选法中价值的最大值
状态转移方程:f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]), k = 0,1,2...s[i]
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int w[N], v[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
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 <= 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]);
cout << f[n][m];
return 0;
}
二进制优化版
优化思路:对于第i种物品,使s[i]用二进制数来分割开来,每个小包就可以只使用一次,从而转化为01背包
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12000, M = 2020;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
int cnt = 0; //记录打包的箱子数
cin >> n >> m;
for(int i = 0; i < n; i ++)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while(k <= s) //这里的等号不取好像也可以
{
cnt ++; //cnt从1开始计数
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;
//01背包优化
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];
return 0;
}
-
分组背包
一共N个物品组,背包容量V,每组物品有多种但可以选
一个
,求背包容纳的最大价值
优化版
f[i][j] = 从前i组物品中选,体积不超过j的所有选法中价值的最大值
状态转移方程:f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]), k = 1,2...s[i]
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
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];
}
for(int i = 1; i <= n; i ++)
for(int j = m; j >= 0; j --) //这里由于k的变化,没有确定的v[i][k], 就不能把它写在循环体的条件里了
{
for(int k = 1; k <= s[i]; k ++) //枚举一组内第k个物品,对每一个都相当于01背包
if(v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
cout << f[m];
return 0;
}