有 N 个物品和一个容量是 V 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。 如下图所示： 如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。 每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。 求解将哪些物品装入背包，可使物品总体积不超过背包容...

有 N 种物品和一个容量是 V 的背包。 物品一共有三类： 第一类物品只能用1次（01背包）； 第二类物品可以用无限次（完全背包）； 第三类物品最多只能用 si 次（多重背包）； 每种体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数...

在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。 为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。  在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。 然而，在网友的国...

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。 输入格式 第一行，包含两个整数n和m。 接下来n行，每行包含一个整数，表示一种货币的面值。 输出格式 共一行，包含一个整数，表示方案数。 数据范围 n≤15,m≤3000 输入样例： 3 10 1 2 5 输出样例： 10 #include <iostream> using names...

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。 今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。 于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。 他还从因特网上查到...

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。 更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。 今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 如果要买归类为附件的物品，必须先买该附件所属的主件。 每个主件可...

总公司拥有 M 台 相同 的高效设备，准备分给下属的 N 个分公司。 各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。 问：如何分配这M台设备才能使国家得到的盈利最大？ 求出最大盈利值。 分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M。 输入格式 第一行有两个数，第一个数是分公司数 N，第二个数是设备台数 M； 接下来是一个 N×...

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行...

潜水员为了潜水要使用特殊的装备。 他有一个带2种气体的气缸：一个为氧气，一个为氮气。 让潜水员下潜的深度需要各种数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。 他完成工作所需气缸的总重的最低限度的是多少？ 例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量： 3 36 120 10 25...