2007-10-02

一个堆积木的算法题，比较有意思，欢迎大家讨论

关键字: 算法

问题的来源是帮一个朋友改数据库，要求是这样的，60个题目，总分是100分，正确答案的分值有2分的 1.5分，其中分值的排列关系是随机的，请问如何设置答对题目，使得答题总分刚好为一个数值，如82分
我的解决办法是：
用一个集合记录判断是正确的2分题，当发现期望总分和当前累加总分差值小于1.5时，因为最小单位是1.5，在2分集合中退出一个正确的2分，然后继续遍历下去
虽然后来用上面办法解决了这个问题，但是我觉得这个问题的解法不够通用，有很多问题，对这个问题扩展了一下，大家一起讨论一下
一维的：和上面的题目一样。用变量来描述一下这个问题
有m个元素，其中每个元素有1个value值，o,value的取值有x，y，z...,按照value值m个元素排列是随机的，问如何用一次遍历m，而得到n个元素，这n个元素的value总和是W
二维的：其实就是俄罗斯方块了，大家想象我们玩的俄罗斯方块是不是这个道理
有m个元素，其中每个元素有1个value值对，o,value的取值有x，y，z...，按照value值m个元素排列是随机的，问如何用一次遍历m，而得到n个元素，这n个元素的value中，v1
的总和乘以v2的总和是W
n维的：不知道用什么现实中的情况来描述了
有m个元素，其中每个元素有1个value值对，o,value的取值有x，y，z...，按照value值m个元素排列是随机的，问如何用一次遍历m，而得到n个元素，这n个元素的value中，v1
的总和乘以v2的总和乘以v3的总和...一直乘到vn的总和是W


呵呵，也许是我孤陋寡闻，上面这个题可能早有算法了，希望知道的朋友能告诉我一声：）


评论
lixiao 2007-10-08
wo~~
不知道我理解的对不对
似乎是背包问题啊～～
你去搜索一下，以前写过这样的程序.
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论

rocket
搜索本博客
最近加入圈子
存档
最新评论