首页 > 其他分享 >Acwing 7. 混合背包问题

Acwing 7. 混合背包问题

时间:2022-12-23 00:44:20浏览次数:34  
标签:good int max 混合 背包 物品 dp Acwing

Acwing 7. 混合背包问题

有 \(N\) 种物品和一个容量是 \(V\) 的背包。

物品一共有三类:

  • 第一类物品只能用 \(1\) 次(01背包);
  • 第二类物品可以用无限次(完全背包);
  • 第三类物品最多只能用 \(s_i\) 次(多重背包);

每种体积是 \(v_i\),价值是 \(w_i\)。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

思路:

根据上文对这三个背包问题的了解,列出他们各自的转移方程

  • 01: \(f[i,j] = max(f[i-1][j],f[i - v[i]] + w[i])\)

  • 多重: \(f[i,j] = max(f[i - 1][j],f[i - 1,j - v[i]],+,...,f[i - 1,j - S_i v[i]] + S_i w[i])\)

  • 完全:\(f[i,j] = max(f[i - 1][j],f[i - 1,j - v[i]],+,...,f[i - 1,j - S v[i]] + S w[i])\)

可知,当前物品的选法,和相应的更新值,和之前的物品类型无关。所以每次判断当前物品的类型,选择对应的转移方程来进行转移就可以了。

通过分析时间复杂度可知,多重背包需要用到二进制优化。

实现:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1005;
int dp[N], n, m;
struct Good
{
    int w, v;
} good[N];

int main()
{
    scanf("%d%d", &n, &m);
    // 遍历物品
    while (n--)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        // 如果可以无数次用,就是完全背包
        if (!s)
            // 遍历体积
            for (int j = v; j <= m; j++)
                dp[j] = max(dp[j], dp[j - v] + w);
        else
        {
            // 将01背包看成可以使用1次的多重背包
            if (s == -1)
                s = 1;

            // 二进制优化多重背包看成01背包
            int cnt = 1;
            for (int i = 1; i <= s; i *= 2)
            {
                good[cnt].v = v * i;
                good[cnt++].w = w * i;
                s -= i;
            }
            // 最后一部分
            if (s > 0)
            {
                good[cnt].v = v * s;
                good[cnt++].w = w * s;
            }

            // 遍历物品
            for (int i = 1; i < cnt; i++)
                // 遍历体积
                for (int j = m; j >= good[i].v; j--)
                    dp[j] = max(dp[j], dp[j - good[i].v] + good[i].w);
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

标签:good,int,max,混合,背包,物品,dp,Acwing
From: https://www.cnblogs.com/zxr000/p/16999868.html

相关文章

  • Acwing 6. 多重背包问题 III
    单调队列优化法从公式入手来看是否还有可以改进的地方\(dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2*v]+2*w,...,dp[i-1][j-s_i*v]+s_i*w)\)我们......
  • Vue中mixin混合
    vue中的mixin可以实现组件中重复代码的高度复用,可以将不同组件中重复的组件选项(如,data、created、mounted、components、computed、watch等)都提取出来,形成一个mixin的js文......
  • Educational DP Contest E - Knapsack 2 (01背包)
    https://atcoder.jp/contests/dp/tasks/dp_e题目大意:有N个物品,编号为1,2,…,N。对于每个i(1≤i≤N),物品I的权重为wi,价值为vi。Taro决定从N件物品中挑选一些,用背包带回家......
  • Acwing 5. 多重背包问题 II
    二进制优化法本质:将多重背包转化为01背包问题思路:暴力法其实相当于把多重背包中的每个物品分成\(s\)个物品,所以才需要那么久的时间复杂度,所以现在想一下有没有什......
  • AcWing342. 道路与航线
    原题链接解题思路这题用\(SPFA\)会被卡,所以我们不能用\(SPFA\)但是观察数据我们可以发现对于道路,\(0≤C_i≤10^{5}\)所以对于每个连通块(内部不存在航线),我们可以用\(Di......
  • Acwing 4. 多重背包问题
    4.多重背包问题I-AcWing题库有\(N\)种物品和一个容量是\(V\)的背包。第\(i\)种物品最多有\(s_i\)件,每件体积是\(v_i\),价值是\(w_i\)。求解将哪些物品装入......
  • 【图像分割】基于收缩系数的粒子群混合引力搜索算法多级图像阈值分割算法研究附matlab
    ......
  • Acwing 第 77 场周赛 ABC(*)
    4716.进球题目大意:整场比赛双方一共打进了n个进球,进球多的一方将收获最终的胜利。请你根据进球纪录,判断哪支球队最终获胜。保证不存在平局。输入样例1:1ABC......
  • 混合云运维,实现批量自动化配置
    随着企业业务规模扩大和复杂化及云计算、大数据等技术不断发展,企业希望通过上云加速其数字化转型,以私有云为数据存储,保障安全,同时兼顾公有云的计算资源,公有云和私有云融合,......
  • 混合模型初探
    混合模型初探1.混合模型简介如果我们定义观测变量和潜在变量的一个联合概率分布,那么对应的观测变量本身的概率分布可以通过求边缘概率的方法得到。......