我观看了动态编程 - Kapsack 问题 (YouTube)。但是，我正在解决一个稍微不同的问题，其中约束是预算、价格、双倍而不是整数。所以我想知道如何修改它？Double 是“连续的”，不像整数，我可以有 1,2,3 ...。我不认为我做 0.0,0.1,0.2 ...？
更新 1
我想通过乘以 100 将 double 转换为 int。钱只有 2 个小数位。但这是否意味着值的范围会非常大？
更新 2
我需要解决的问题是：
商品具有价格（双）和满意度（整数）值。我有预算作为约束，我需要最大限度地提高满意度。
在 youtube 视频中，作者创建了两个二维数组，如 int[numItems][possibleCapacity(weight)]。在这里，我不能因为预算是双倍而不是整数
如果您想使用具有任意精度的浮点数（即，没有固定的小数位数），并且这些不是分数，动态编程将不起作用。
动态规划的基础是存储特定输入的先前计算结果。因此，如果您使用具有任意精度的浮点数，则实际上每个可能的浮点数都需要无限的内存，当然，还需要进行无限的计算，这是不可能且非最佳的。
但是，如果这些数字具有固定的精度（就像货币一样，只有两个十进制数字），您可以通过将它们相乘来将它们转换为整数（正如您所提到的），然后照常解决背包问题。
您必须按照您在更新 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），视频中的人也无法（手动）解决他的问题。
这不是您问题的答案，但也可能是您正在寻找的：
我使用Microsoft 的 Solver Foundation 3制作了一个简单的代码来解决您描述的问题。它不使用背包算法，而是单纯形法。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;
namespace LPOptimizer
{
class Item
{
public String ItemName { get; set; }
public double Price { get; set; }
public double Satisfaction { get; set; }
static void Main(string[] args)
{
//Our data, budget and items with respective satisfaction and price values
double budget = 100.00;
List<Item> items = new List<Item>()
{
new Item(){
ItemName="Product_1",
Price=20.1,
Satisfaction=2.01
},
new Item(){
ItemName="Product_2",
Price=1.4,
Satisfaction=0.14
},
new Item(){
ItemName="Product_3",
Price=22.1,
Satisfaction=2.21
}
};
//variables for solving the problem.
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
Term goal = 0;
Term constraint = 0;
foreach (Item i in items)
{
Decision decision = new Decision(Domain.IntegerNonnegative, i.ItemName);
model.AddDecision(decision); //each item is a decision - should the algorithm increase this item or not?
goal += i.Satisfaction * decision; //decision will contain quantity.
constraint += i.Price * decision;
}
constraint = constraint <= budget; //this now says: "item_1_price * item_1_quantity + ... + item_n_price * item_n_quantity <= budget";
model.AddConstraints("Budget", constraint);
model.AddGoals("Satisfaction", GoalKind.Maximize, goal); //goal says: "Maximize: item_1_satisfaction * item_1_quantity + ... + item_n_satisfaction * item_n_quantity"
Solution solution = context.Solve(new SimplexDirective());
Report report = solution.GetReport();
Console.Write("{0}", report);
Console.ReadLine();
}
}
}
这找到了具有价格（双倍）和预算约束（双倍）的项目数量（整数）的最佳最大值。
从代码中，很明显您可以拥有一些实际值（双）的项目数量。这也可能比具有大范围的背包更快（如果您决定使用您提到的 *100）。
您可以轻松指定其他约束（例如某些项目的数量等...）。上面的代码改编自此 MSDN How-to，其中展示了如何轻松定义约束。
我突然想到您可能没有使用 C#，在这种情况下，我相信有许多用于多种语言的线性编程库，并且都相对简单易用：您指定约束和目标。
根据您的Update 2，我已更新此代码以包含满意度。
你看过这个。抱歉，我没有评论权限。
编辑 1
你是说约束是预算而不是背包重量？这仍然是一个背包问题。
或者你说的不是整数的项目值（ 0-1背包问题）你有分数。然后贪婪的方法应该做得很好。
编辑 2
如果我正确理解您的问题..它说明
我们有n各种各样的项目，从 1 到 n。每种物品i都有价值vi和价格pi。我们通常假设所有的价值和价格都是非负的。预算是B。
该问题最常见的表述是0-1 knapsack problem，它将xi每种项目的副本数限制为 0 或 1。在数学上，0-1-背包问题可以表述为：
n
maximize E(vi.xi)
i=i
n
subject to E(pi.xi) <= B, xi is a subset of {0,1}
i=1
Neo Adonis 的答案就在这里。动态编程在实践中无法实现任意精度。
但是，如果您愿意将精度限制为小数点后 2 位.. 然后按照视频中的说明进行操作.. 您的表格应该看起来像这样..
+------+--------+--------+--------+--------+--------+--------+
| Vi,Pi| 0.00 | 0.01 | 0.02 | 0.03 | 0.04 ... B |
+------+--------+--------+--------+--------+--------+--------+
|4,0.23| | | | | | |
|2,2.93| | | | | | |
|7,9.11| | | | | | |
| ... | | | | | | |
| Vn,Pn| | | | | | answer |
+------+--------+--------+--------+--------+--------+--------+
正如您所提到的，您甚至可以将实数转换为 int。
是的，取值范围非常大，你也得明白背包是NP-complete，即没有有效的算法来解决这个问题。唯一pseudo polynomial使用 DP 的解决方案。看到这个和这个。
最近发布到 sci.op-research 的一个问题让我从一些我不想去想而你也不想听到的乏味工作中得到了一个可喜的喘息机会。我们知道，贪心启发式求解连续背包问题最大化c′xs.ta′x≤bx≤ux∈ℜ+n(1)到最优。（证明，使用对偶理论，很容易。）假设我们添加一个我称之为计数约束的东西，产生 Maximizec′xs.ta′x≤be′x=b~x≤ux∈ℜ+n(2 ) 其中 e=(1,…,1) 。是否可以通过单纯形法以外的方法解决，例如贪心启发式的变体？
答案是肯定的，尽管我完全不确定我想出的方法是否比单纯形法更容易编程或更有效。就个人而言，我会链接到带有线性规划求解器的库并使用单纯形法，但找到替代方案很有趣，即使替代方案可能不是单纯形法的改进。
我将介绍的方法依赖于对偶，特别是一个众所周知的结果，如果一个线性规划的可行解和它的对偶的可行解满足互补松弛条件，那么两者在各自的问题中都是最优的。我将分别表示背包和计数约束 λ 和 μ 的对偶变量。请注意，λ≥0 但 μ 在符号上不受限制。本质上，下面所述的相同方法适用于不等式计数约束（e'x≤b~），实际上会稍微容易一些，因为我们会先验地知道 μ（非负）的符号。原始问题的海报指定了一个相等计数约束，所以这就是我将使用的。上限也有对偶变量（ρ≥0）。对偶问题是最小化bλ+b～μ+u′ρs.t.λa+μe+ρ≥cλ,ρ≥0.(3)
这是一篇博文而不是论文，我将假设 (2) 是可行的，所有参数都是严格正数，并且最优解是唯一的且不会退化。唯一性和简并性不会导致算法无效，但它们会使表示复杂化。在 (2) 的最优基本可行解决方案中，将有一个或两个基本变量——一个如果背包约束是非绑定的，两个如果它是绑定的——每个其他变量都是非基本变量的下限或上限。假设 (λ,μ,ρ) 是 (2) 的对偶的最优解。任何变量 xi 的降低成本是 ri=ci−λai−μ 。如果背包约束是非约束性的，则λ=0，最优解是xi=uiri>0b～-∑rj>0ujri=00ri<0。(4) 如果背包约束是约束性的，则有两个项目(j , k ），其变量是基本的， rj=rk=0 。（通过假设没有退化，我假设背包约束中的松弛变量是基本的值为0的可能性）。设 xi=uiri>00ri<0(5) 并令 b′=b−∑i∉{j,k}aixi 和 b~′=b~−∑i∉{j,k}xi 。两个基本变量由 xj=b′-akb～′aj-akxk=b′-ajb～′ak-aj 给出。 (6)
该算法将分两个阶段进行，首先寻找具有背包非绑定（一个基本 x 变量）的解决方案，然后寻找具有背包绑定（两个基本 x 变量）的解决方案。请注意，我们第一次找到服从互补松弛的可行原始和对偶解决方案时，两者都必须是最优的，所以我们完成了。还要注意，给定任何 μ 和任何 λ≥0 ，我们可以通过设置 ρi=ci−λai−μ+ 来完成它以获得 (3) 的可行解。因此，我们将始终处理可行的对偶解，并且该算法将构造满足互补松弛度的原始解。因此，停止标准简化为构造的原始解决方案是可行的。
对于第一阶段，我们对变量进行排序，使得 c1≥⋯≥cn 。由于 λ=0 并且存在单个基本变量 (xh )，其降低成本必须为零，显然 μ=ch 。这意味着 xi 的降低成本 ri=ci−λai−μ=ci−ch 对于 ih 是非负的。如果 (3) 给出的解是可行的——也就是说，如果 ∑ih 。因此我们可以使用二分搜索来完成这个阶段。如果我们假设 n 的值很大，则初始排序可以在 O(nlogn) 时间内完成，而该阶段的其余部分需要 O(logn) 次迭代，每次迭代都使用 O(n) 次。
不幸的是，我没有看到将二等分搜索应用于第二阶段的方法，在该阶段中，我们寻找背包约束为绑定且 λ>0 的解决方案。我们将再次搜索 μ 的值，但这次是单调的。首先将贪心启发式应用于问题（1），保留背包约束但忽略计数约束。如果解决方案偶然满足计数约束，我们就完成了。但是，在大多数情况下，将违反计数约束。如果计数超过 b~ ，那么我们可以推断 (4) 中 μ 的最优值为正；如果计数低于 b~ ，则 μ 的最佳值为负。我们以 μ=0 开始第二阶段，并朝着最优值的方向移动。
由于贪心启发式对项目进行排序使得 c1/a1≥⋯≥cn/an ，并且由于我们从 μ=0 开始，因此我们当前的排序顺序为 (c1−μ)/a1≥⋯≥(cn−μ)/an . 当我们搜索 μ 的最佳值时，我们将保留该排序（根据需要重新排序）。为避免混淆（我希望如此），让我假设 μ 的最佳值为正，这样我们将不断增加 μ。我们正在寻找 (λ,μ) 的值，其中 x 变量中有两个是基本变量，这意味着两个变量的成本降低了 0。假设 xi 和 xj 发生这种情况；那么ri=0=rj⟹ci-λai-μ=0=cj-λaj-μ(7)⟹ci-μai=λ=cj-μaj。很容易证明（留给读者作为练习）如果 (c1−μ)/a1≥⋯≥(cn−μ)/an 对于 μ 的当前值，则 μ 的下一个更高（更低）值在 (7) 中创建平局必须涉及连续的一对连续项目 (j=i+1 )。而且，再次摆脱退化（在这种情况下意味着超过两个项目的成本降低为 0），如果我们将 μ 略微超过项目 i 和 i+1 降低成本 0 的值，排序顺序的唯一变化是项目i 和 i+1 交换位置。再往那个方向移动不会导致 i 和 i+1 再次打成平手，但当然，他们中的任何一个最终都可能与路上的新邻居打成平手。
第二阶段，从 μ=0 开始，进行如下。对于每一对 (i,i+1)，计算 μ 的值 μi，其中 (ci−μ)/ai=(ci+1−μ)/ai+1 ；如果该值小于 μ 的当前值（表示平局发生在错误的方向），则将该值替换为 ∞。将 μ 更新为 miniμi ，从 (7) 计算 λ，并从 (5) 和 (6) 计算 x。如果 x 是原始可行的（减少到 0≤xi≤ui 和 0≤xi+1≤ui+1 ），则 stop: x 是最优的。否则按排序顺序交换 i 和 i+1，设置 μi=∞（重新索引的项目 i 和 i+1 不会再次绑定）并重新计算 μi-1 和 μi+1（没有其他 μj 受交换影响）。
如果第一阶段没有找到最优值（并且如果第二阶段开始时的贪婪启发式算法没有走运），则第二阶段必须以最优值结束，然后才能检查出 μ 值（所有 μj= ∞ )。可以通过在编码中付出一点额外努力来处理退化（例如，当出现三向或更高的关系时，在第二阶段检查 i 和 j 的多个组合）或通过进行小扰动来打破退化。
答案并不完全正确。
您可以实现一个动态程序，以整数满足和任意实数奖品（如双打）来解决背包问题。
首先是整数奖问题的标准解：
Define K[0..M, 0..n] where K[j, i] = optimal value of items in knapsack of size j, using only items 1, ..., i
for j = 0 to M do K[j,0] = 0
for i = 1 to n do
for j = 0 to M do
//Default case: Do not take item i
K[j,1] = K[j, i-1]
if j >= w_i and v_i+K[j-w, i-1] > K[j, i] then
//Take item i
K[j,i] = v_i + K[j-w_i, i-1]
这将创建一个表，可以通过遵循条目 K[M, n] 的递归来找到解决方案。
现在解决实数权重问题：
Define L[0..S, 0..N] where L[j, i] = minimal weight of items in knapsack of total value >= j, using only items 1, ..., i
and S = total value of all items
for j = 0 to S do L[j, 0] = 0
for i = 0 to n do
for j = 0 to S do
//Default case: Do not take item i
L[j,i] = L[j, i-1]
if j >= v_i and L[j-v_i, i-1] + w_i < L[j, i] then
//Take item i
L[j, i] = L[j -v_i, i-1] + w_i
现在可以找到与其他版本类似的解决方案。我们现在不使用重量作为第一维度，而是使用导致最小重量的项目的总值。该代码具有或多或少相同的运行时间 O(S * N)，而另一个具有 O(M * N)。
您的问题的答案取决于几个因素：
如果您有非常大的约束值（远超过数百万）和非常多的项目（远超过数千）
那么唯一的选择就是贪心逼近算法。按每单位重量价值的递减顺序对物品进行排序，然后按此顺序包装。
如果您想使用简单的算法并且不需要很高的精度
然后再次尝试使用贪心算法。“满意度值”本身可能是非常粗略的近似值，所以当简单的近似值可能就足够时，为什么还要费心发明复杂的解决方案。
如果您有非常大（甚至连续）的约束值，但项目数量很少（少于数千）
然后使用分支定界方法。您不需要从头开始实施它。试试GNU GLPK。它的分支切割求解器并不完美，但可能足以解决小问题。
如果约束值和项目数都很小
使用任何方法（DP、分支和绑定，或者只是蛮力）。
如果约束值非常小（小于数百万）但项目太多（如数百万）
那么DP算法是可能的。
最简单的情况是无界背包问题，当每种物品的副本数量没有上限时。这篇维基百科文章很好地描述了如何简化问题：UKP 中的优势关系以及如何解决它：无界背包问题。
更困难的是0-1背包问题，即每种物品只能打包零次或一次。而有界背包问题，允许将每种物品打包到某个整数限制时间则更加困难。互联网为这些问题提供了很多实现，在同一篇文章中有几个建议。但是不知道哪个好哪个坏。