背包问题 - 信奥网|信息学奥赛

0推荐

848浏览

信息学奥赛一本通T1296：背包问题开餐馆

【题目描述】信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n个地点排列在同一条直线上。我们用一个整数序列m1,m2,...mn来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。【输入】输入第一

0
轩爸发布于 2020-05-06 16:20

0推荐

899浏览

信息学奥赛一本通T1295：背包问题装箱问题

【题目描述】有一个箱子容量为V（正整数，0≤v≤20000），同时有n个物品（0< n ≤30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。【输入】第一行是一个整数V，表示箱子容量。第二行是一个整数n，表示物品数。接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。【输出】一个整数，表示箱子剩余空间。【输入样例】24【

0
轩爸发布于 2020-05-06 10:20

0推荐

600浏览

信息学奥赛一本通T1294：背包问题 Charm Bracelet

【题目描述】有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。【输入】第1行:两个整数，n(物品数量，n≤3500)和m(背包容量,m≤12880)。第2..n+1行：：每行二个整数w[i]，c[i]，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输入样例】4 6

0
轩爸发布于 2020-05-06 10:20

0推荐

996浏览

信息学奥赛一本通T1293：背包问题买书

【题目描述】小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？【输入】第一行为n和m。一个整数 n，代表总共钱数。（0 ≤ n ≤ 1000）【输出】一行，方案数。【输入样例】20【输出样例】2【源程序】

0
轩爸发布于 2020-05-06 10:20

0推荐

812浏览

信息学奥赛一本通T1292：背包问题宠物小精灵之收服

【题目描述】宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因

0
轩爸发布于 2020-05-06 10:20

2推荐

1060浏览

信息学奥赛一本通T1291：背包问题数字组合

【题目描述】有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如：n=5,5个数分别为1,2,3,4,5，t=5；那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。【输入】输入的第一行是两个正整数n和t，用空格隔开，其中1≤n≤20,表示正整数的个数，t为要求的和(1≤t≤1000);接下来的一行是n个正整数，用空格隔开。【输出】和为t的不同的组合方式的数目。【输入样例】5

0
轩爸发布于 2020-05-06 10:20

0推荐

581浏览

信息学奥赛一本通T1290：背包问题采药

【题目描述】辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果

0
轩爸发布于 2020-05-05 16:20

0推荐

825浏览

信息学奥赛一本通T1273：背包问题货币系统

【题目描述】给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。【输入】第一行为n和m。【输出】一行，方案数。【输入样例】3 10 //3种面值组成面值为10的方案【输出样例】10 //有10种方案【源程序】

0
轩爸发布于 2020-05-04 10:20

0推荐

472浏览

信息学奥赛一本通T1271：背包问题潜水员

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

0
轩爸发布于 2020-05-04 10:20

1推荐

624浏览

信息学奥赛一本通T1272：背包问题分组背包

【题目描述】一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。【输入】第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；第2..N

0
轩爸发布于 2020-05-04 10:20

2推荐

735浏览

信息学奥赛一本通T1270：背包问题混合背包

【题目描述】一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。【输入】第一行：二个整数，M(背包容量，M≤200)，N(物品

0
轩爸发布于 2020-05-03 16:20

1推荐

1060浏览

信息学奥赛一本通T1269：背包问题庆功会

【题目描述】为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。【输入】第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均

0
轩爸发布于 2020-05-03 16:20

0推荐

672浏览

信息学奥赛一本通T1268：背包问题完全背包问题

【题目描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。【输入】第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输

0
轩爸发布于 2020-05-03 16:20

0推荐

1048浏览

信息学奥赛一本通T1267：背包问题 01背包问题

【题目描述】一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。【输入】第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输入样例】10 4【输出样

0
轩爸发布于 2020-05-03 16:20