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

AcWing.7 混合背包问题

时间:2022-12-25 21:57:39浏览次数:51  
标签:多重 背包 int qquad 混合 AcWing.7 01 物品

题目描述

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

物品一共有三类:

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

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

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

解题思路

\(\qquad\)由于多重背包经过二进制拆分之后会变成以\(2^k\)为数量的\(log_2{s_i}\)堆,我们可以在这些堆上做\(01\)背包,所以我们就把这个混合背包搞成了两类:

\(\qquad\)\(a.s_{i}=0\),此时在题目的描述中是完全背包,做一遍完全就行。

\(\qquad\)\(b.s_{i}\neq 0\)此时我们就是\(01\)或者多重了,那\(01\)我们可以看成是每个物品最多用\(1\)次,也就是所有的\(s_i\)都是\(1\),然后做二进制优化的多重背包即可

代码

#include <iostream>

using namespace std;

const int N = 1010;
int f[N], n, m;

int main() 
{
    scanf("%d%d", &n, &m);
        
    for (int i = 1; i <= n; i ++ ) 
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        
        if (s == 0) //当完全背包做
        {
            for (int j = v; j <= m; j ++ ) 
                f[j] = max(f[j], f[j - v] + w);
        }
        else //转化为01背包
        {
            if (s == -1) s = 1;
            
            for (int k = 1; k <= s; k <<= 1) 
            {
                for (int j = m; j >= v * k; j -- ) 
                    f[j] = max(f[j], f[j - v * k] + w * k);
                s -= k;
            }
            
            if (s) for (int j = m; j >= s * v; j -- )
                f[j] = max(f[j], f[j - v * s] + w * s);
        }
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

\(\color{Green}{顺利AC!}\)

标签:多重,背包,int,qquad,混合,AcWing.7,01,物品
From: https://www.cnblogs.com/StkOvflow/p/17004658.html

相关文章

  • 背包模型
    背包模型概述​最长上升子序列:序列DP(相邻两个被选择的有关系)背包问题:组合DP,在全局的考虑之下最小f[i][j]:i表示搞了多少,j表示限制集合:所有仅仅从前i个物品当中选......
  • 【221224PH-1】两种物质的密度为P1和P2,各取一定质量混合,若混合后密度为(P1+P2)/2,且混合
    ......
  • Acwing 12. 背包问题求具体方案
    Acwing12.背包问题求具体方案01背包问题,但是要求输出字典序最小的方案数。思路:状态转移方程:\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])\)求具体......
  • P1757 通天之分组背包
    P1757通天之分组背包有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(C_i\),价值是\(W_i\)。这些物品被划分为\(K\)组,每组中的物品互相冲突,最......
  • 基于容器的PaaS混合云的几种形式
    概述这是Gartner的一个图,提供了全球的基于容器的PaaS公有云、混合云服务的梳理展示:这里提供一个其他的视角:中国市场,基于容器的PaaS混合云(公有云+私有云)的相关......
  • Acwing 7. 混合背包问题
    Acwing7.混合背包问题有\(N\)种物品和一个容量是\(V\)的背包。物品一共有三类:第一类物品只能用\(1\)次(01背包);第二类物品可以用无限次(完全背包);第三类物品最多......
  • 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\)个物品,所以才需要那么久的时间复杂度,所以现在想一下有没有什......