【算法与数据结构】——动态规划（2）

谁借莪１个温暖的怀抱￠ 2022-09-02 00:46 236阅读 0赞

多重背包

给定n种物品，每种物品都有重量wi和价值vi，每种物品的数量都可以大于1但是有限制。第i种物品有ci个，背包容量为W，求解在不超过背包容量的情况下如何放置物品，可以使背包中物品的价值之和最大。

解决方法

  1. 暴力拆分
    指将第i种物品看做ci中独立的物品，每种物品只有一个，转化为01背包问题。时间复杂度O(W ∑ c i \sum c_i ∑ci​）

    for(int i = 1;i <= n;i++)
    for(int k = 1;k <= c[i];k++)
    for(int j = W;j >= w[i];j—)
    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

  2. 二进制拆分
    算法比较麻烦，优化也不是最优，暂时先不记录

  3. 数组优化
    用一个数组num[j]记录容量为j时放入了多少个第i种物品，以满足物品数量限制。
    算法代码：

    for int(i = 1;i <= n;i++)
    {
    memset(num,0,sizeof(num));
    for(int j = w[i];j <= w;j++)
    { if(dp[j] < dp[j-w[i]]+v[i]&&num[j-w[i]]<c[i]){
    dp[j] = dp[j-w[i]]+v[i];
    num[j] = num[j-w[i]]+1;
    }}}

分组背包

给定n租物品，第i组有ci个物品，第i组的第j个物品有重量wij和价值vij，背包容量为W，在不超过背包容量的情况下每组最多选择一个物品，求解如何放置物品可使背包中物品的价值之和最大。dp[i][j]表示将前i种物品放入容量为j的背包中获得的最大价值。

  1. for(int i = 1;i <= n;i++)
  2. for(int j = W;j >= 0;j--)
  3. for(int k = 1;k <= c[i];k++)
  4. { if(j >= w[i][k])
  5. { dp[j] = max(dp[j],dp[j-w[i][k]]+v[i][k]);
  6. }}

混合背包

如果在一个问题中有些物品只可以去一次(01背包），有些物品可以取无限次（完全背包），有些物品可以去有限次（多重背包），则该问题属于混合背包问题。解决问题的关键是识别出问题中的子问题，用对应的背包问题求解，将困难问题转化为简单问题。
例题：

发表评论

表情：
评论列表 （有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读