# 背包问题 #
  • AcWing 10. 有依赖的背包问题

    有 N 个物品和一个容量是 V 的背包。 物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。 如下图所示: 如果选择物品 5,则必须选择物品 1 和 2。这是因为 2 是 5...

    刷题记录
  • AcWing 487. 金明的预算方案

    金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。 更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。 今天一早,金明就开始做预算了,他把想...

    刷题记录
  • AcWing 12. 背包问题求具体方案

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 \(v_i\),价值是 \(w_i\)。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 最优选法的...

    刷题记录
  • AcWing 11. 背包问题求方案数

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 \(v_i\),价值是 \(w_i\)。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 最优选法的...

    刷题记录
  • AcWing 1013. 机器分配

    总公司拥有 M 台 相同 的高效设备,准备分给下属的 N 个分公司。 各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。 问:如何分配这 M 台设备才能使国家得到的盈利最大? 求出最大盈利值。...

    刷题记录
  • AcWing 1020. 潜水员

    潜水员为了潜水要使用特殊的装备。 他有一个带 2 种气体的气缸:一个为氧气,一个为氮气。 让潜水员下潜的深度需要各种数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作...

    刷题记录
  • AcWing 8. 二维费用的背包问题

    有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。 每件物品只能用一次。体积是 \(v_i\),重量是 \(m_i\),价值是 \(w_i\)。 求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超...

    刷题记录
  • AcWing 7. 混合背包问题

    有 N 种物品和一个容量是 V 的背包。 物品一共有三类: 第一类物品只能用1次(01背包); 第二类物品可以用无限次(完全背包); 第三类物品最多只能用 \(s_i\) 次(多重背包); 每种体积是 \(...

    刷题记录
  • 倍数问题

    题目 众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。 但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。 现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数,使得这三个数的和是 K 的...

    刷题记录