华为oj 购物单

    xiaoxiao2025-01-19  12

    其实,这种给定总量,求在规定总量内价值最大是多少,这是典型的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吧,祝自己能找个好工作。

    转载请注明原文地址: https://ju.6miu.com/read-1295622.html
    最新回复(0)