具有连续(非独特)约束的背包

Question

我观看了动态编程 - Kapsack问题(YouTube).但是,我正在解决一个稍微不同的问题,其中约束是预算,价格,是双倍,而不是整数.所以我想知道如何修改它？双是"连续"不像整数,我可以有1,2,3 ....我不认为我做0.0,0.1,0.2 ......？

更新1

我想通过乘以100将double转换为int.Money只有2位小数.但这意味着价值范围会非常大？

更新2

我需要解决的问题是:

物品具有价格(双倍)和满意度(整数)值.我有预算作为约束,我需要最大化满意度.

在youtube视频中,作者创建了两个2d数组,如int [numItems] [possibleCapacity(weight)].在这里,我不能预算是一个双重不整数

Answer 1

如果要使用具有任意精度的浮点数(即,没有固定的小数位数),并且这些不是分数,则动态编程将不起作用.

动态编程的基础是存储特定输入的计算的先前结果.因此,如果您使用具有任意精度的浮点数,则每个可能的浮点数都需要几乎无限的内存,当然,还要进行无限计算,这是不可能的,也是非最优的.

但是,如果这些数字具有固定的精度(与货币一样,只有两个十进制数),您可以通过乘以它们(如您所述)将它们转换为整数,然后像往常一样解决背包问题.

Answer 2

你将不得不做你在更新1中所说的内容:以美分表示预算和项目价格(假设我们在谈论美元).那我们不是在谈论任意精度或连续数字.每个价格(和预算)都是一个整数,只是整数代表美分.

为了简化操作,我们假设预算为10美元.该问题是,背包的容量将不得不采取一切值:

[0.00, 0.01, 0.02, 0.03, ..., 9.99, 10.00] 

价值观是两个.SOLUTION MATRIX和KEEP MATRIX的每一行都有1001列,因此您无法手动解决问题(如果预算是数百万美元,即使计算机可能有困难),但这是固有的原始问题(你不能做任何事情).

你最好的选择是使用一些关于KNAPSACK的现有代码,或者自己编写代码(我不建议).

如果您找不到关于KNAPSACK的现有代码并且熟悉Linux/Mac,我建议您安装GNU线性编程套件(GLPK)并将问题表达为整数线性程序或二进制线性程序(如果您正在尝试解决0-1背包).它将为您解决问题(如果需要,您可以通过C,C++,Python和Java使用它).有关使用GLPK的帮助,请查看这篇非常棒的文章(您可能需要第2部分,其中讨论整数变量).如果您需要有关GLPK的更多帮助,请发表评论.

编辑:

基本上,我想说的是你的约束不是连续的,它是离散的(美分),你的问题是预算可能是太多的分数,所以你将无法手工解决它.

不要被吓倒,因为你的预算可能是几美元 - >几百美分.如果您的预算仅为18美分,则问题的大小将与YouTube视频中的大小相当.如果他的背包尺寸为1800(甚至180),视频中的人也无法(手动)解决他的问题.