Tag: 背包问题
分支和绑定背包实现的内存扼流圈
我从这里开始编写基于伪Java代码的分支和绑定背包算法的实现。 不幸的是，这个问题的大型实例会让内存窒息。 为什么是这样？ 如何使此实现更节省内存？ 链接上文件的输入格式如下： numberOfItems maxWeight profitOfItem1 weightOfItem1 . . . profitOfItemN weightOfItemN // http://books.google.com/books?id=DAorddWEgl0C&pg=PA233&source=gbs_toc_r&cad=4#v=onepage&q&f=true import java.util.Comparator; import java.util.LinkedList; import java.util.PriorityQueue; class ItemComparator implements Comparator { public int compare (Object item1, Object item2){ Item i1 = (Item)item1; Item i2 = (Item)item2; if ((i1.valueWeightQuotient)<(i2.valueWeightQuotient)) return 1; if ((i2.valueWeightQuotient)<(i1.valueWeightQuotient)) return -1; else { // costWeightQuotients are […]
背包问题的可能组合和？
好快速概述 我调查了背包问题 http://en.wikipedia.org/wiki/Knapsack_problem 我知道这是我的项目所需要的，但我项目的复杂部分是我需要在一个主要的麻袋里放多个麻袋。 拿着所有“袋子”的大背包只能携带x个“袋”（例如，为了举例说明9个）。 每个包都有不同的价值; 重量 成本 尺寸 容量 依此类推，所有这些值都是整数。 让我们假设0-100。 内袋也将被分配一种类型，并且在外袋中只能有一种类型，尽管程序输入将被赋予多个相同类型。 我需要指定主包可以容纳的最大重量，小包的所有其他属性需要按加权值分组。 例 外袋： 可容纳9个小包 重量不超过98 [任何一方给予或取5] 必须保持每种类型中的一种，一次只能容纳一种类型。 内袋： 成本，加权100％ 尺寸，加权为67％ 容量，加权44％ 该程序将提供多个袋子的输入，然后必须计算出更小的袋子的组合进入更大的袋子，根据输入将有多种解决方案，并且程序将为我输出最佳解决方案。 我想知道你们认为对我来说最好的办法是什么。 我将用Java或C＃编程。 我很乐意用PHP编程，但我担心这种算法对于Web服务器效率非常低。 谢谢你提供的所有帮助 -Zack
我该如何解决？ KnapSack – 值全部相同，但每个其他对象有三个权重
解决我的运动有问题。 我读到了动态编程和算法，我认为我的练习是“特定的背包问题”。 我用蛮力方法解决了它，但我无法用动态编程解决它。 我有一艘有300吨重量的船（背包）。 存在晶体本身具有3种物质（X，Y，Z） – 彼此物质具有重量并且所有晶体具有相同的值。 我需要打包尽可能多的水晶，但所有包装晶体的物质比例必须是1：1：1。 但是，例如，如果我有三个比例为1：1：1的晶体，它们产生最大的吨数，八个晶体产生相同数量的晶体（另外两个晶体组合产生最大吨数），我需要选择具有最少数量晶体的组合。 我用蛮力方法解决了它 – 我创建了一个包含所有组合的数组列表。 接下来，我发现它们以1：1：1的比例组合。 接下来，我发现这种组合产生了最大的吨数，并且具有最少的晶体数量（如果有两个或更多组合具有相同的最大吨数）。 我检查了测试，它返回了很好的分数，我不知道如何用动态编程解决它; /有人帮我吗？ 例如，当我有10个晶体时： 1) X =2 Y =3 Z =4 2) X =5 Y=10 Z =2 3) X =3 Y =3 Z =3 4) X =1 Y =0 Z =6 5) X =9 Y=12 Z =4 6) X =1 Y =1 […]
背包01扭曲
我在Java中做背包，我们只使用权重而没有价值。 重量限制是1000.我们从键盘扫描了5个重量，我们使用。 扭曲的是，你可以实际超过1000，从壁橱到1000.所以在一个场景中我们有2个可能的重量990和1010，并且程序可以选择较高的一个。 扫描的数字永远不会高于1000。 package kapsackidone; import java.util.Scanner; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.*; public class Kapsack { public static void main(String[] args) throws Exception { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int [] wt=new int[5]; int W = 1000; System.out.println(“Enter Weight 5 weights”); for(int i=0; i<5; i++) { wt[i]=Integer.parseInt(reader.readLine()); } System.out.println(knapsack(wt, W)); } public static int […]
0-1多维背包
因此，我正在尝试生成一种算法，该算法将找到n项的最佳组合（在我的情况下为4），只能在背包中放置一次（0-1）并具有最大重量容量。 可能更有效地概括，我想在我的背包中放置不超过四个独特的物品，以便它们的重量小于某个值W，同时最大化它们的总价值。 我的第一次尝试和假设是将体积限制为4，所有项目体积为1，用于多维背包问题。 但我遇到的问题是它不是0-1（意思是否在袋中）。 然后我尝试制作一个多维的0-1（有界）背包代码，但我无法添加音量限制以及0-1要求。 如何编写0-1多维背包问题？ 或者我如何调整代码只保留一个V卷，所有项目卷为1？ 代码不一定是Java，但这就是我到目前为止所拥有的。 背包： package hu.pj.alg; import hu.pj.obj.Item; import java.util.*; public class ZeroOneKnapsack { protected List itemList = new ArrayList(); protected int maxWeight = 0; protected int solutionWeight = 0; protected int profit = 0; protected boolean calculated = false; public ZeroOneKnapsack() {} public ZeroOneKnapsack(int _maxWeight) { setMaxWeight(_maxWeight); } public […]
如何确保Java线程在不同的核心上运行
我正在用Java编写一个multithreading应用程序，以提高顺序版本的性能。 它是0/1背包问题的动态编程解决方案的并行版本。 我有一个Intel Core 2 Duo，在不同的分区上同时使用Ubuntu和Windows 7 Professional。 我在Ubuntu中运行。 我的问题是并行版本实际上需要比顺序版本更长的时间。 我想这可能是因为线程都被映射到同一个内核线程或者它们被分配到同一个内核。 有没有办法确保每个Java线程映射到一个单独的核心？ 我已经阅读了有关此问题的其他post，但似乎没有任何帮助。 这是KnapsackThread类（扩展Thread）的main（）和run（）的结束。 请注意，我使用slice和extra来计算myLowBound，myHiBound确保每个线程不会在dynProgMatrix的域中重叠。 因此没有竞争条件。 dynProgMatrix = new int[totalItems+1][capacity+1]; for (int w = 0; w<= capacity; w++) dynProgMatrix[0][w] = 0; for(int i=0; i<=totalItems; i++) dynProgMatrix[i][0] = 0; slice = Math.max(1, (int) Math.floor((double)(dynProgMatrix[0].length)/threads.length)); extra = (dynProgMatrix[0].length) % threads.length; barrier = new CyclicBarrier(threads.length); for (int i […]
