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

谁借莪１个温暖的怀抱￠ 2022-09-02 00:46 177阅读 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]);

1.  二进制拆分  
    算法比较麻烦，优化也不是最优，暂时先不记录
2.  数组优化  
    用一个数组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的背包中获得的最大价值。

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

# 混合背包 #

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