首页 文章
  • 1 votes
     answers
     views

    如何从所有强力组合中找到最佳解决方案?

    我想从字典的所有蛮力组合中找到最佳解决方案 . 对于问题的背景,我需要找出在给定重量限制的情况下运输所有奶牛所需的最小行程数 . 已经通过辅助函数 get_partitions 给了我这些组合 . 该函数返回一个嵌套列表,每个内部列表代表一次旅行以及该行程中的奶牛名称 . 助手功能: def partitions(set_): if not set_: yield [] ...
  • 1 votes
     answers
     views

    寻找有关理解特定组合优化问题的建议

    给定一组项目(大小在1到100之间)和多个箱子(1到15) . 每个项目具有可以分配项目的箱子集,并且优先排序哪个箱子最好,第二好,等等,只是为了它 . 项目也有一个自然顺序,下面用命名表示,例如item2之前的item1 . 每个箱子的容量在1到5之间(每个物品具有相同的重量,即1) . 一个示例输入可以是三个箱子和六个物品( - 表示箱子不在物品的可用集合中,即不能用它打包): | bin1 ...
  • 0 votes
     answers
     views

    背包算法变异

    我有一个以下问题: 有一组项目,每个项目有2个不同的正值A和B. 背包有两个值:totalA和totalB . 这是所选项目的值A和B的最大总和 . 我必须知道,背包可以容纳的最大物品数是多少 . Example: Input: 总计:10,总计B:15 item1 A:3,B:4 item2 A:7,B:2 item3 A:1,B:9 item4 A:2,B:1 item5 A:4,B:6 Ou...
  • 1 votes
     answers
     views

    这类似于背包还是改变算法?

    这个问题涉及尝试将不同重量的物品装入袋子中,以使袋子以指定的总重量或最接近总的指定重量结束 . Example 1 :- Bag can hold max up to 240 kg of weight Item1-60kg,Item2-30kg,Item3-55kg,Item4-60kg,Item5-80kg,Item6-40kg,Item7- 7kg, 这里选择的项目应该是Item1,Ite...
  • 0 votes
     answers
     views

    具有多个重量和价格具有约束上限的物品的背包

    我试图解决以下问题,并想知道是否存在任何适合解决此问题的背包算法的变化 问题: 一个小偷进入房子的意图是,偷东西 . 他需要x Kg的银,y Kg的金和z Kg的钻石 . 房子里有许多由金,银和钻石制成的物品 . 每个项目可以包含任何数量的这些元素(即,它可以是纯金,或金和银的合金,或金和钻石的合金等) . 每个商品都附有价格标签 . 现在,我们的小偷是一个正直的男人,他不希望主人受到太大的伤害...
  • 0 votes
     answers
     views

    硬币更换功能使用无界背包python

    我正在尝试写一个硬币更换功能 . 我的想法是,我有无限的面额和任何 Value ,并试图看到我能得到什么样的改变 . 我认为这可以像一个无限的背包程序,但我得到一个奇怪的输出,我不明白这意味着什么 . 我想也许是因为我输入了值和小数,并且想要将函数中的值更改为float但是这给了我一个错误并且不会运行程序 . 有人可以解释我目前的输出说的是什么吗?是否有可能用小数做这种事情?我怎样才能改善这个? ...
  • -1 votes
     answers
     views

    使用动态规划的 Value 无关背包问题

    我搜索了所有网站 . 但背包问题总是与权重和 Value 观有关 . 我必须为以下问题编写算法和C实现.. 问题: 背包问题是给定一组正整数(a1,.....,an)和大小为s的背包,找到(a1,.....,an)的子集A,使得元素之和在A中最大但最多是s . 必须使用动态编程来设计算法 . 还必须证明正确性并且必须为此计算计算时间 . 你能为此提供任何有用的资源吗?任何人都可以解释如何做到这一点...
  • 1 votes
     answers
     views

    balancer 分区与背包1/0的复杂性

    balancer 分区: . 你有一组n个整数,每个都在0 ... K范围内 . 将这些整数划分为两个子集,以便最小化| S1 - S2 |,其中S1和S2表示两个子集中每个子集中元素的总和 . 背包问题:给定一组具有权重和值的项目,确定要包含在集合中的每个项目的数量,以使总权重小于或等于给定限制,并且总值与可能 . 不能两次使用同一个对象 . 似乎 balancer 分区问题的解决方案是简单...
  • 4 votes
     answers
     views

    最小化颜色:背包算法的变体?

    在一个项目上工作我遇到了这个问题,我将在问题的真正领域之外进行重新讨论(我想我可以谈论烟花和形状的口径,但它会使理解更加复杂化) . 我正在寻找一种(可能是近似的)算法来解决它 . 我有n个不同大小的容器,m个具有不同大小职业和不同颜色的对象(对象可以是多色的,因此对象的颜色确实是一组) . 我的目标是将所有物体装入容器中(我已经知道这是可能的),这样每个容器的颜色种类最少 . 随着“各种颜色的最...
  • 2 votes
     answers
     views

    0-1背包有额外限制(彩色物品)?

    我正在解决这个问题主要是出于对工作中停工的好奇心 . 想象一下正常的0-1背包问题,除了所有项目都是黄色,红色,蓝色或绿色,并且由于你的OCD,你的背包中每种颜色必须正好有两项 . 因此,除了正常项目,每个项目都有3个属性:权重,值,颜色 . 这甚至还是背包问题,还是以其他方式更好地定义?
  • 0 votes
     answers
     views

    嵌套背包 - 一个背包中的多个背包

    甚至可以实施吗? 这种情况是否有所不同? 我需要在c#中编写代码 这个问题有点困难;我确实编写了代码来填充背包,目前正在尝试编写代码以填充多个背包 . 但目前我的情况如下: 有10个大盒子 每个大箱子有不同的允许重量(外背包) 每个大箱子有不同数量的容器(内背包) 有一袋球 每个球都有资格被放置在几个不同的容器中 球的重量与内背包不同 现在我需要将球分成...
  • 3 votes
     answers
     views

    背包但确切的重量

    是否有算法来确定具有精确重量W的背包?即这就像正常的0/1背包问题,n个项目各有权重w_i和值v_i . 最大化所有项目的 Value ,但是 total weight of the items in the knapsack need to have exactly weight W ! 我知道“普通”0/1背包算法,但这也可以返回一个重量更轻但 Value 更高的背包 . 我想找到最高值但确切...
  • 2 votes
     answers
     views

    多项有界背包算法

    我有一个项目列表,每个项目都有一个价格 - 或者在背包问题方面,一个权重 . 可购买物品的数量仅受预算限制,因此只要消耗的总量不超过某个常数,就可以购买尽可能多的物品 . 我还有一个算法,根据某些变量,告诉每个项目的盈利程度(即每个项目的 Value ) . 所以基本上我有一个有限的背包问题,额外的条件是每个项目不止一个适合背包 . 我想在这些条件下最大化利润 . 我知道没有一个有效的解决方案,但...
  • 0 votes
     answers
     views

    具有1D阵列的动态编程USACO训练:子集总和

    在解决USACO培训问题时,我发现了动态编程 . 处理这个概念的第一个训练问题是一个叫做子集和的问题 . The Problem Statement Follows : 对于从1到N的多组连续整数(1 <= N <= 39),可以将该组分成两组,其总和相同 . 例如,如果N = 3,则可以以一种方式对集合{1,2,3}进行分区,以使两个子集的总和相同: {3}和{1,2} 这被视为单...

热门问题