标题:贪心算法求解这道题
只看楼主
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
回复 44楼 beyondyf
别搞笑啦,错误百出?

我就是真命天子,顺我者生,逆我者死!
2015-06-10 17:34
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
回复 45楼 BlueGuy
你是要我给你分析分析呢?还是要跟我扣百这个字眼?

没上一百,毕竟你才写了几句。我能理解你不懂这个成语的意思。哦,严格地说它不算成语,是句俗语。

重剑无锋,大巧不工
2015-06-10 17:56
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
回复 46楼 beyondyf
我想听听你怎么分析

我就是真命天子,顺我者生,逆我者死!
2015-06-10 17:58
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
回复 48楼 边小白
你就不要起哄啦,估计你这辈子都看不懂我写的代码了

我就是真命天子,顺我者生,逆我者死!
2015-06-10 18:20
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
那个求和代码可以去掉,直接由递归来计算,
递归函数里的第2个循环也能去掉,我写的比较仓促,
还没来的及整理代码

这段代码是正确无误的,只是效率稍微差一点。
真子集还能有漏网之鱼么?

[ 本帖最后由 BlueGuy 于 2015-6-10 21:45 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2015-06-10 21:35
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
唉,不知该说你什么好。你自珍重。

先跟王姑娘说两句。VC6实在太老了,还是尽快换个新的吧。他的items的初始化方式在C++98标准下是错误的(VC6连98都支持的不完善,毕竟它也诞生于98年),但在C++11下是正确的。

当然他的代码也不完整,直接编译肯定不过。至少还要加个#include <vector> 和 unsing namespace std;

这些语法级的毛病我也懒得追究,开始顺着往下讲,以下的“你”均指代蓝小子。

items、isSelect、selected三个向量分别用来存储元素集、被选择元素标志集,以及被选择元素集。尤其这个selected,让我吐了,这等再往下用的时候再解释。

cap是背包的容量,selectedMax用来记录实际最多装了多少。

你滥用全局变量及vector这些毛病也不提了,跟你谈什么内聚耦合估计也是白扯。

divide的函数,以递归的方式穷举所有的装入背包的组合方式。这个想法本身就是愚蠢的。别人这么写我不会说什么,你怎么说也号称写过几年程序了,就这水平?

2的n次方这种效率,三四十个元素的计算就让人无法忍受了。一千个?你投胎转世个几千次它也算不完(你别不服,需要的话我可以给你计算)。

而且连个剪枝过程都没有,一定要到最后一个元素才开始统计和。当找到一组更大的组合的时候这处理方式vector要是会吐它一定吐了。还先清空再一个一个添进去,整个数组不比这轻省得多?

而且selected里存的居然是元素值。当时看到这里时我一愣,等看到main里用到selected时我吐了。

再说说divide里这一层一层的括号,跟狗啃过似的好看吗?代码没几行,括号倒占了不少行,尤其当时我在手机上看的那叫个费劲。你这里有五对括号毛线用都没有白白占了十行。

你们公司代码是不是按行收费的?如果是,那我就理解了。

终于到主函数了。

count就是你用来统计用几个背包的。

愚蠢的while(true)。你把里面的if(items.size() == 0)的条件取反放在while的条件里好不好?尽整些脱裤子那啥的事。

整个循环的目的是每次找一个最优背包,然后删掉它接着找,直到所有物品都装完了,数数装过几个背包,典型的贪心思维。我已经说过这是不行的,你不听我也没办法。

count++的位置也不好。你考虑过你背包里压根一件物品下装不下的情况吗?

之后选出一个大背包,之后从元素集里删除已经装入背包的元素。

哦,这是你想要做的,但你的代码并不会按你的想法运作。

你知道items中的元素是可以重复的吧?

你觉得
if (items[j] == selected[i])
这句会怎么执行?它能删除几个items[j]?想想就反胃,不解释了。

再下一句,你会用vector吗?

items.earse(items.begin() + j);执行后会删除第j个元素。这时原来的第j+1个元素已经变为第j个元素。到for迭代的j++后实际j索引的已经是原来的第j+2个元素。和你想的一样吗?

算了,反正前一句已经错了,这句也无所谓了。

if已经在前面说过。

selectedMax = 0; 这种初始化语句就不该放在这里,这个变量就不该用全局变量,太业余了。

之后四句全是废话,写了还不如不写。也更说明你压根不了了解vector该怎么用。好好区分一下size和capacity的区别。

最后。你连一句输出都没有,程序运行完能干什么?逗CPU玩呢?

总结。就你这两行直白的代码,也就唬唬学语言没两天的,靠那几层括号撑门面呢。别说什么一辈子看不懂这样幼稚的话,我初中时写的算法也比你这复杂。

你踏踏实实写代码我不会这样损你。我不欺负不懂的人,只是看不惯没有自知之明的人。很久没写这么多了,就到这儿吧。

重剑无锋,大巧不工
2015-06-10 22:05
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
回复 50楼 beyondyf
初中的时候,你连子集都不知道是什么概念

我就是真命天子,顺我者生,逆我者死!
2015-06-10 22:13
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
回复 51楼 BlueGuy
我真懒得理你了,抓紧弄你的代码吧。别再发乱七八糟的东西,我不关心你的学习进度。

重剑无锋,大巧不工
2015-06-10 22:22
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
据说,曾经微软有一次考试,让程序员写一个2分查找,结果没有一个人写对。
我能写成这样已经很不错了

我就是真命天子,顺我者生,逆我者死!
2015-06-10 22:27
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
虽然就几行代码,但是需要学过数据结构 2叉树才能看的懂。
不过,我上班之后就没在学算法了,现在的水平还是我在学校的水平,
还只停留在DFS 和 BFS之上。

我开始优化代码了,

[ 本帖最后由 BlueGuy 于 2015-6-11 00:08 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2015-06-10 23:00



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-445925-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.051375 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved