贪心算法背包问题设有n=8个体积分别为54,45,43,29,23,21,14,1的物体和一个容积为C=110的背包,问

梦回夫涯2022-10-04 11:39:541条回答

贪心算法背包问题
设有n=8个体积分别为54,45,43,29,23,21,14,1的物体和一个容积为C=110的背包,问选择哪几个物体装入背包可以使其装的最满 C/c++程序

已提交，审核后显示！提交回复

China_rock 共回答了21个问题 | 采纳率100%: 缺少物品的价值.; 1年前

贪心算法中,通常会让证明贪心选择性,请问,证明贪心选择性的实质是什么?怎样说明一个问题具有贪心选择呢 anna504319961年前1: ly_luo 共回答了12个问题 | 采纳率83.3%

贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来得到.
就是说,你需要证明当前问题可以通过选择最好的那个元素（比如01背包,总能够通过选择当前重量最小的物品来得到最优解）来解决问题
证明：（每一步所做的贪心选择最终导致问题的整体最优解）
//基本思路：考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解
1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解；
2,数学归纳法证明每一步均可通过贪心选择得到最优解

1年前查看全部

假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场.设计一个有效的贪心算法进行安排. 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场.设计一个有效的贪心算法进行安排. 备注：如果觉得程序有点繁琐的话就不用写出程序了,只要写出算法的思想就好了,不过要写详细一些,要有具体的表达式等, 三十八抽1年前0: 共回答了个问题 | 采纳率

查看全部

跪求高手献上此题的算法（Pascal只要算法不要程序）【不要用贪心算法，用普通数组】 跪求高手献上此题的算法（Pascal只要算法不要程序）【不要用贪心算法，用普通数组】 合并果子【不要贪心算法】 Description 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。　　每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。　　因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。　　例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 Input 输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 30000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。 Output 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。 Sample Input Copy 3 1 2 9 Sample Output Copy 15 HINT 【数据规模】 对于30%的数据，保证有n <= 100； 对于50%的数据，保证有n <= 5000； 对于全部的数据，保证有n <= 30000。 Source 神经克克1年前1: 若星汉天空共回答了17个问题 | 采纳率88.2%

这道题可以先排个序，每次选最小的两堆合并，就这样。
显然，先合并的比后合并的多算了一次重量，所以应该轻的先合并，你拿重量1的多算一次肯定比重量9的多算一次划算嘛~

1年前查看全部

此题求翻译,好像是关于贪心算法的 此题求翻译,好像是关于贪心算法的 FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. 倒地葫芦1年前1: 糖伯虎共回答了16个问题 | 采纳率93.8%

确实是贪心算法的,物品是可分的.肥鼠有M磅猫食,准备跟把守仓库的猫交换,仓库里存放着它最喜欢的食物javabean.仓库有N个房间,第i个房间存储了J[i]磅的javabean,需要F[i]磅猫食才能等价交换.肥鼠没有必要换出房间的所有javabean,而是可以只付出F[i]*a%磅的猫食,换回J[i]*a%的javabean.现在它把这个任务交给你,告诉它可以得到的最大数量的javabean.

1年前查看全部

求教一道贪心算法的问题假设一长途汽车路上有n个站点并从1开始顺序编号1,2,……,n,其中起点站为1,终点站为n,旅客可 求教一道贪心算法的问题 假设一长途汽车路上有n个站点并从1开始顺序编号1,2,……,n,其中起点站为1,终点站为n,旅客可以从任一个站i上车(1 素芭的跟班1年前1: tctga 共回答了14个问题 | 采纳率85.7%

貌似用不到贪心吧?
要求最少需要多少辆汽车只需确定最多有多少个乘客同时在车上就成了
算法如下：
1,定义a[n][n]用于存储p(i,j),则i行的和为i站上车的人数,j列的和为j站下车的人数；
2,任意站点i开车时乘客人数f(i)=f(i-1)-d(i)+u(i),其中d(i)表示下车人数,u(i)表示上车人数,明显f(0)=0；
3,从i=1开始到i=n-1结束,遍历,得到最多乘车的乘客数目max,需要的车数=max/30 向上取整.

1年前查看全部

假设有7个物品,它们的重量和价值如下表所示.若这些物品均可以被分割,且背包容量M＝140,使用贪心算法求解此背包问题.W 假设有7个物品,它们的重量和价值如下表所示.若这些物品均可以被分割,且背包容量M＝140,使用贪心算法求解此背包问题.W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30） cmz8881年前1: sdfasdfergewd 共回答了13个问题 | 采纳率84.6%

w(i)=（35,30,50,60,40,10,25）
p(i)=（10,40,30,50,35,40,30）
p(i) / w(i)=( 2/7, 4/3, 3/5, 5/6, 7/8 ,4, 6/5)
x(i)=(1, 1, 0 ,0 ,1 ,1 ,1)
（求和公式）w(i)x(i0=35*1+30*1+50*0+60*0+40*1+10*1+25*1=140
(求和公式)p(i)x(i)=10*1+40*1+30*0+50*0+35*1+40*1+30*1=155
即背包的最优解是（1, 1, 0 ,0 ,1 ,1 ,1）
最大收益是155
（大概就是这样吧,不知道有没有计算错误,自己再看一下吧）

1年前查看全部

贪心算法背包问题设有n=8个体积分别为54,45,43,29,23,21,14,1的物体和一个容积为C=110的背包,问

共1条回复

相关推荐

大家在问