算法:5 维费用背包问题
时间复杂度:$O(100 \times 6^5)$
可以看成是一个完全背包问题的多维扩展题。
f[ ][ ][ ][ ][ ] 的每一维代表 {m0, m1, m2, m3, m4} 的物品个数,其中物品个数最多为 $5$ 个,其值代表最小费用。
需要注意的是,{1, 0, 0, 0, 0},{0, 1, 0, 0, 0}......,费用为 $p$ 也是一种优惠方式,所以最后一定有解,可以计算得出来,其次是编号问题,用哈希表将其映射到 [0,4] 之间即可,方便表示和计算。
多维费用的完全背包问题和我们之前的一维完全背包问题的思路是一摸一样的,只不过在更新的时候,因为需要处理输入,所以每次只是进行单独更新,其实和我们之前的更新是一模一样的(体积 + 价值)。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 6;
int n, cnt;
int f[N][N][N][N][N];
unordered_map <int, int> ids;
int get(int x)
{
if (ids.count(x) == 0) ids[x] = cnt++;
return ids[x];
}
void update(int v[], int p)
{
for (int a = v[0]; a < 6; ++a) {
for (int b = v[1]; b < 6; ++b) {
for (int c = v[2]; c < 6; ++c) {
for (int d = v[3]; d < 6; ++d) {
for (int e = v[5]; e < 6; ++e) {
f[a][b][c][d][e] = min(f[a][b][c][d][e], f[a - v[0]][b - v[1]][c - v[2]][d - v[3]][e - v[4]] + p);
}
}
}
}
}
}
int main()
{
cin >> n;
memset(f, 0x3f, sizeof(f));
f[0][0][0][0][0] = 0;
while (n--) {
int v[5] = {0};
int m, p;
cin >> m;
while (m--) {
int c, k;
cin >> c >> k;
v[get(c)] += k;
}
cin >> p;
update(v, p);
}
int b, m[5] = {0};
cin >> b;
while (b--) {
int v[5] = {0};
int c, k, p;
cin >> c >> k;
m[get(c)] = k;
v[get(c)] = 1; // 1 个商品,可以看作是一种优惠方式
cin >> p;
update(v, p);
}
cout << f[m[0]][m[1]][m[2]][m[3]][m[4]] << endl;
return 0;
}
找到一个BUG updete函数中e的那一行初始化应为v[4]
终于找到一个也用
for (int a, b, c ...)
而不是for (int i, j, k ...)
的人 :D