华为oj 购物单

其实,这种给定总量，求在规定总量内价值最大是多少，这是典型的01背包问题，当然这道题加了一点其他的东西，就是主件附件，只有主件已经购买才能买附件，那我们就在加入附件之前判断一下主件是否已经购买了就可以了，所以这道题我们应该分两部分解决。

1.实现经典的01背包算法（动态规划）

2.在循环过程中，如果遇到附件，判断其主件是否已经存在，若存在可以购买。

对于经典的01背包问题，可以直接问度娘，很多博客有介绍，很详细，下面直接给出状态方程

F[i][j] = max(F[i-1][j] , F[i-1][j-w[i]] + V[i])

其中w[i]为当前重量，在此程序中就是第i件（物品的钱数），v[i]为当前价值，在此程序中就是（当前钱数乘以重要度）

对于第二部分我们需要建立一个标记数组 flag[i][j]，来统计某个物品是否出现过，所以在当前物品是附件的时候直接查看flag[i] [ j - w[i] ]是否为true，即可知道主件是否存在。 下面直接给出代码

#include<iostream> #include<fstream> #include<vector> #include<algorithm> using namespace std; #define MAX_N 2000 #define MAX_M 20 struct goods { int v; int p; int q; }; int main() { int value, num, i, j, v, p, q, w; goods g; vector<goods> goodsList; int f[MAX_M][MAX_N]; bool flag[MAX_M][MAX_N]; //初始化 memset(f, 0, MAX_M * MAX_N * sizeof(int)); memset(flag, false, MAX_M * MAX_N * sizeof(bool)); cin >> value >> num; for (i = 0; i<num; i++) { cin >> g.v >> g.p >> g.q; goodsList.push_back(g); } for (i = 1; i <= num; i++) { for (j = 0; j <= value; j++) { w = goodsList[i - 1].v*goodsList[i - 1].p; if (goodsList[i - 1].q == 0) { if (j < goodsList[i - 1].v) { f[i][j] = f[i - 1][j]; } else { flag[i][j] = true; f[i][j] = max(f[i - 1][j], f[i - 1][j - goodsList[i - 1].v] + w); } } else { if (j < goodsList[i - 1].v) { f[i][j] = f[i - 1][j]; } else { if (flag[i][j - goodsList[i - 1].v]) { f[i][j] = max(f[i - 1][j], f[i - 1][j - goodsList[i - 1].v] + w); } else { f[i][j] = f[i - 1][j]; } } } } } cout << f[num][value] << endl; return 0; }

还有半个月就要开始各种各样的面试工作了，抓紧时间再刷一遍华为oj吧，祝自己能找个好工作。