概览
N件物品,容量V, 重量M
求将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且总价值最大
在约束条件上多了一维
题解
01背包、完全背包、多重背包的综合
是否对模型本身进行改变,状态进行了改变
f[i,j,k]
所有只从前i个物品中选择,并且总体积不超过j,总重量不超过k的选法集合
最大值
f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+w[i])
其实这里所有不包含物品i的选法有很多种情况,本身就能用f[i-1,j-v1[i],k-v2[i]]来概括了
二维费用可以和所有背包问题合并在一起
求方案数也可以和所有背包问题合并在一起
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, V, M;
int f[N][N];
int main() {
cin >> n >> V >> M;
for (int i = 0; i < n; i ++) {
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j --)
for (int k = M; k >= m; k --)
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
cout << f[V][M] << endl;
return 0;
}
6哦!
为什么不用拉格朗日乘数线性规划法,非要暴力穷举K种集合。要是物品的数量多起来,计算时间大大增加啊
啥是拉格朗日乘数线性规划法
简单,给力,创新!