具有连续(非不同)约束的背包

发布于 2024-12-27 05:49:20 字数 555 浏览 0 评论 0原文

我观看了动态规划 - 卡普萨克问题 (YouTube)。然而,我正在解决一个稍微不同的问题,其中约束是预算、价格,双倍而不是整数。所以我想知道如何修改它? Double 是“连续的”,不像整数,我可以有 1,2,3 .... 我不认为我会做 0.0, 0.1, 0.2 ...?

更新1

我想通过乘以100将double转换为int。金钱只有小数点后两位。但这是否意味着数值范围会很大?

更新2

我需要解决的问题是:

物品有价格(双倍)和满意度(整数)值。我有预算作为限制,我需要最大化满意度值。

在 youtube 视频中,作者创建了两个二维数组,如 int[numItems][possibleCapacity(weight)]。在这里,我不能,因为预算是双精度而不是整数

I watched Dynamic Programming - Kapsack Problem (YouTube). However, I am solving a slightly different problem where the constraint is the budget, price, in double, not integer. So I am wondering how can I modify that? Double is "continuous" unlike integer where I can have 1,2,3 .... I don't suppose I do 0.0, 0.1, 0.2 ...?

UPDATE 1

I thought of converting double to int by multiply by 100. Money is only 2 decimal places. But that will mean the range of values will be very large?

UPDATE 2

The problem I need to solve is:

Items have a price (double) & satisfaction (integer) value. I have a budget as a constraint and I need to maximize satisfaction value.

In the youtube video, the author created two 2d array like int[numItems][possibleCapacity(weight)]. Here, I can't as budget is a double not integer

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

掩于岁月 2025-01-03 05:49:20

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

动态规划的基础是存储特定输入的先前计算结果。因此,如果您使用任意精度的浮点数,则每个可能的浮点数实际上都需要无限的内存,并且当然会进行无限的计算,这是不可能且非最佳的。

但是,如果这些数字具有固定的精度(就像金钱一样,只有两位小数),您可以通过将它们相乘来将它们转换为整数(正如您所提到的),然后像往常一样解决背包问题。

If you want to use floating point numbers with arbitrary precision (i.e., don't have a fixed number of decimals), and these are not fractions, dynamic programming won't work.

The basis of dynamic programming is to store previous results of a calculation for specific inputs. Therefore, if you used floating point numbers with arbitrary precision, you would need practically infinite memory for each of the possible floating point numbers and, of course, do infinite calculations, something that is impossible and non-optimal.

However, if these numbers have a fixed precision (as with the money, which only have two decimal numbers), you can convert these into integers by multiplying them (as you've mentioned), and then solve the knapsack problem as usual.

悲凉≈ 2025-01-03 05:49:20

您必须执行您在更新 1 中所说的操作:以美分表示预算和商品价格(假设我们谈论的是美元)。那么我们不是在谈论任意精度或连续数。每个价格(和预算)都是一个整数,只是该整数代表美分。

为了方便起见,我们假设预算为 10 美元。 问题是背包容量必须采用以下所有值:

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

这些值有两个。解决方案矩阵和保持矩阵的每一行都有 1001 列,因此您将无法手动解决问题(如果预算为数百万美元,即使是计算机也可能会遇到困难) )但这是原始问题所固有的(您对此无能为力)。

您的最佳选择是使用一些有关 KNAPSACK 的现有代码,或者编写您自己的代码(我不建议这样做)。

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

编辑:

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

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

You will have to do what you said in UPDATE 1: express the budget and item prices in cents (assuming we are talking about dollars). Then we're not talking about arbitrary precision or continuous numbers. Every price (and the budget) will be an integer, it's just that that integer will represent cents.

To make things easier let's assume the budget is $10. The problem is that the Knapsack Capacity will have to take all the values in:

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

The values are two many. Each line of the SOLUTION MATRIX and the KEEP MATRIX will have 1001 columns so you won't be able to solve the problem by hand (if the budget is millions of dollars even a computer might have a hard time) but that is inherent to the original problem (you can't do anything about it).

Your best bet is to use some existing code about KNAPSACK or maybe write your own (I don't advice that).

If you can't find existing code about KNAPSACK and are familiar with Linux/Mac I suggest you install the GNU Linear Programming Kit (GLPK) and express the problem as an Integer Linear Program or a Binary Linear Program (if you're trying to solve the 0-1 Knapsack). It will solve the problem for you (plus you can use it through C, C++, Python and maybe Java if you need to). For help using GLPK check this awesome article (you'll probably need part 2, where it talks about integer variables). If you need more help with GLPK please leave a comment.

EDIT:

Basically, what I'm trying to say is that your constraint is not continuous, it's discrete (cents), your problem is that the budget might be too many cents so you won't be able to solve it by hand.

Don't get intimidated because your budget might be several dollars -> several hundreds of cents. If your budget is just 18 cents your problem's size will be comparable to the one in the YouTube video. The guy in the video wouldn't be able to solve his problem either (by hand) if his knapsack size was 1800 (or even 180).

把人绕傻吧 2025-01-03 05:49:20

这不是您问题的答案,但也可能是您正在寻找的内容:

线性编程

我使用过的 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 操作指南,其中显示了如何轻松定义约束。

编辑

我发现您可能没有使用 C#,在这种情况下,我相信许多语言都有许多用于线性编程的库,并且使用起来都相对简单:您指定约束和目标。

Edit2

根据您的更新2,我已更新此代码以包含满意度。

This is not an answer to your question, but might as well be what you are looking for:

Linear Programming

I've used Microsoft's Solver Foundation 3 to make a simple code that solves the problem you described. It doesn't use the knapsack algorithm, but a simplex method.

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();
        }
    }
}

This finds the optimum max for the number of items (integers) with prices (doubles), with a budget constraint (double).

From the code, it is obvious that you could have some items quantities in real values (double). This will probably also be faster than a knapsack with a large range (if you decide to use the *100 you mentioned).

You can easily specify additional constraints (such as number of certain items, etc...). The code above is adapted from this MSDN How-to, where it shows how you can easily define constraints.

Edit

It has occurred to me that you may not be using C#, in this case I believe there are a number of libraries for linear programming in many languages, and are all relatively simple to use: You specify constraints and a goal.

Edit2

According to your Update 2, I've updated this code to include satisfaction.

×纯※雪 2025-01-03 05:49:20

看看这个
抱歉,我没有评论权限。

编辑 1

您是说约束是预算而不是背包重量吗?
这仍然是一个背包问题。

或者你说的不是物品值,而是整数(0-1背包问题),你有分数。那么贪心方法应该就可以了。

编辑2

如果我正确理解你的问题..它指出

我们有n种项目,1到n。每种商品i都有一个值vi和一个价格pi。我们通常假设所有价值和价格都是非负的。预算为B

该问题最常见的表述是0-1背包问题,它将每种物品的副本数量xi限制为零或一。从数学上讲,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 的答案 很准确这里..动态规划在实践中不适用于任意精度。

但是,如果您愿意将精度限制为小数点后两位..然后按照视频中的说明进行操作..您的表格应该看起来像这样..

+------+--------+--------+--------+--------+--------+--------+
| 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完全的,即没有有效的算法来解决这个问题。唯一使用 DP 的伪多项式解决方案。请参阅这个

Have your looked at this.
Sorry, I don't have comment privilege.

Edit 1

Are you saying constraint is the budget instead of knapsack weight?
This still remains a knapsack problem.

Or are your saying instead of Item Values as Integers(0-1 knapsack problem) your have fractions. Then Greedy approach should do fine.

Edit 2

If I understand your problem correctly.. It states

We have n kinds of items, 1 through n. Each kind of item i has a value vi and a price pi. We usually assume that all values and pricess are nonnegative. The Budget is B.

The most common formulation of the problem is the 0-1 knapsack problem, which restricts the number xi of copies of each kind of item to zero or one. Mathematically the 0-1-knapsack problem can be formulated as:

         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's answer is spot on here.. Dynamic programming wont work for arbitrary precision in practice.

But if you are willing to limit the precision say to 2 decimal places.. then carry on as explained in video.. your table should look something like this..

+------+--------+--------+--------+--------+--------+--------+
| 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 |
+------+--------+--------+--------+--------+--------+--------+

you can even convert real numbers to int as you have mentioned.

Yes, the range of values is very large, and you also have to understand knapsack is NP-complete, i.e, there is no efficient algorithm to solve this. only pseudo polynomial solution using DP. see this and this.

银河中√捞星星 2025-01-03 05:49:20

最近发布在 sci.op-research 上的一个问题让我从一些我不想去想、你也不想听到的乏味工作中得到了喘息的机会。我们知道贪心启发式解决了连续背包问题
最大化c′xs.ta′x≤bx≤uxεℜ+n(1)
达到最优。 (使用对偶理论的证明非常简单。)假设我们添加我所说的计数约束,产生
最大化c′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 ;如果该值小于 μ 的当前值(表明平局发生在错误的方向),则用 Infinity 替换该值。将 μ 更新为 miniμi ,根据 (7) 计算 λ,并根据 (5) 和 (6) 计算 x。如果 x 是原始可行的(简化为 0≤xi≤ui 和 0≤xi+1≤ui+1 ),则停止: x 是最优的。否则按排序顺序交换 i 和 i+1,设置 μi=∞(重新索引的项 i 和 i+1 不会再次并列)并重新计算 μi−1 和 μi+1(没有其他 μj 受到交换的影响)。

如果第一阶段没有找到最优值(并且如果第二阶段开始时的贪婪启发式运气不佳),则第二阶段必须在用完要检查的 μ 值之前以最优值终止(所有 μj=无穷大)。可以通过在编码中付出一点额外的努力来处理简并性(例如,当发生三向或更高关系时,在第二阶段检查 i 和 j 的多种组合),或者通过进行小的扰动来打破简并性。

A question recently posted to sci.op-research offered me a welcome respite from some tedious work that I’d rather not think about and you’d rather not hear about. We know that the greedy heuristic solves the continuous knapsack problem
maximizec′xs.t.a′x≤bx≤ux∈ℜ+n(1)
to optimality. (The proof, using duality theory, is quite easy.) Suppose that we add what I’ll call a count constraint, yielding
maximizec′xs.t.a′x≤be′x=b˜x≤ux∈ℜ+n(2)
where e=(1,…,1) . Can it be solved by something other than the simplex method, such as a variant of the greedy heuristic?

The answer is yes, although I’m not at all sure that what I came up with is any easier to program or more efficient than the simplex method. Personally, I would link to a library with a linear programming solver and use simplex, but it was amusing to find an alternative even if the alternative may not be an improvement over simplex.

The method I’ll present relies on duality, specifically a well known result that if a feasible solution to a linear program and a feasible solution to its dual satisfy the complementary slackness condition, then both are optimal in their respective problems. I will denote the dual variables for the knapsack and count constraints λ and μ respectively. Note that λ≥0 but μ is unrestricted in sign. Essentially the same method stated below would work with an inequality count constraint (e′x≤b˜ ), and would in fact be slightly easier, since we would know a priori the sign of μ (nonnegative). The poster of the original question specified an equality count constraint, so that’s what I’ll use. There are also dual variables (ρ≥0 ) for the upper bounds. The dual problem is
minimizebλ+b˜μ+u′ρs.t.λa+μe+ρ≥cλ,ρ≥0.(3)

This being a blog post and not a dissertation, I’ll assume that (2) is feasible, that all parameters are strictly positive, and that the optimal solution is unique and not degenerate. Uniqueness and degeneracy will not cause invalidate the algorithm, but they would complicate the presentation. In an optimal basic feasible solution to (2), there will be either one or two basic variables — one if the knapsack constraint is nonbinding, two if it is binding — with every other variable nonbasic at either its lower or upper bound. Suppose that (λ,μ,ρ) is an optimal solution to the dual of (2). The reduced cost of any variable xi is ri=ci−λai−μ . If the knapsack constraint is nonbinding, then λ=0 and the optimal solution is
xi=uiri>0b˜−∑rj>0ujri=00ri<0.(4)
If the knapsack constraint is binding, there will be two items (j , k ) whose variables are basic, with rj=rk=0 . (By assuming away degeneracy, I’ve assumed away the possibility of the slack variable in the knapsack constraint being basic with value 0). Set
xi=uiri>00ri<0(5)
and let b′=b−∑i∉{j,k}aixi and b˜′=b˜−∑i∉{j,k}xi . The two basic variables are given by
xj=b′−akb˜′aj−akxk=b′−ajb˜′ak−aj.(6)

The algorithm will proceed in two stages, first looking for a solution with the knapsack nonbinding (one basic x variable) and then looking for a solution with the knapsack binding (two basic x variables). Note that the first time we find feasible primal and dual solutions obeying complementary slackness, both must be optimal, so we are done. Also note that, given any μ and any λ≥0 , we can complete it to obtain a feasible solution to (3) by setting ρi=ci−λai−μ+ . So we will always be dealing with a feasible dual solution, and the algorithm will construct primal solutions that satisfy complementary slackness. The stopping criterion therefore reduces to the constructed primal solution being feasible.

For the first phase, we sort the variables so that c1≥⋯≥cn . Since λ=0 and there is a single basic variable (xh ), whose reduced cost must be zero, obviously μ=ch . That means the reduced cost ri=ci−λai−μ=ci−ch of xi is nonnegative for ih . If the solution given by (3) is feasible — that is, if ∑ih . Thus we can use a bisection search to complete this phase. If we assume a large value of n , the initial sort can be done in O(nlogn ) time and the remainder of the phase requires O(logn) iterations, each of which uses O(n) time.

Unfortunately, I don’t see a way to apply the bisection search to the second phase, in which we look for solutions where the knapsack constraint is binding and λ>0 . We will again search on the value of μ , but this time monotonically. First apply the greedy heuristic to problem (1), retaining the knapsack constraint but ignoring the count constraint. If the solutions happens by chance to satisfy the count constraint, we are done. In most cases, though, the count constraint will be violated. If the count exceeds b˜ , then we can deduce that the optimal value of μ in (4) is positive; if the count falls short of b˜ , the optimal value of μ is negative. We start the second phase with μ=0 and move in the direction of the optimal value.

Since the greedy heuristic sorts items so that c1/a1≥⋯≥cn/an , and since we are starting with μ=0 , our current sort order has (c1−μ)/a1≥⋯≥(cn−μ)/an . We will preserve that ordering (resorting as needed) as we search for the optimal value of μ . To avoid confusion (I hope), let me assume that the optimal value of μ is positive, so that we will be increasing μ as we go. We are looking for values of (λ,μ) where two of the x variables are basic, which means two have reduced cost 0. Suppose that occurs for xi and xj ; then
ri=0=rj⟹ci−λai−μ=0=cj−λaj−μ(7)⟹ci−μai=λ=cj−μaj.
It is easy to show (left to the reader as an exercise) that if (c1−μ)/a1≥⋯≥(cn−μ)/an for the current value of μ , then the next higher (lower) value of μ which creates a tie in (7) must involve consecutive a consecutive pair of items (j=i+1 ). Moreover, again waving off degeneracy (in this case meaning more than two items with reduced cost 0), if we nudge μ slightly beyond the value at which items i and i+1 have reduced cost 0, the only change to the sort order is that items i and i+1 swap places. No further movement in that direction will cause i and i+1 to tie again, but of course either of them may end up tied with their new neighbor down the road.

The second phase, starting from μ=0 , proceeds as follows. For each pair (i,i+1) compute the value μi of μ at which (ci−μ)/ai=(ci+1−μ)/ai+1 ; replace that value with ∞ if it is less than the current value of μ (indicating the tie occurs in the wrong direction). Update μ to miniμi , compute λ from (7), and compute x from (5) and (6). If x is primal feasible (which reduces to 0≤xi≤ui and 0≤xi+1≤ui+1 ), stop: x is optimal. Otherwise swap i and i+1 in the sort order, set μi=∞ (the reindexed items i and i+1 will not tie again) and recompute μi−1 and μi+1 (no other μj are affected by the swap).

If the first phase did not find an optimum (and if the greedy heuristic at the start of the second phase did not get lucky), the second phase must terminate with an optimum before it runs out of values of μ to check (all μj=∞ ). Degeneracy can be handled either with a little extra effort in coding (for instance, checking multiple combinations of i and j in the second phase when three-way or higher ties occur) or by making small perturbations to break the degeneracy.

爺獨霸怡葒院 2025-01-03 05:49:20

答案并不完全正确。

您可以实现一个动态程序,以整数满足和任意实数奖品(如双打)来解决背包问题。

首先是整数奖励问题的标准解决方案:

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)。

The answers are not quite correct.

You can implement a dynamic programm that solves the knapsack problem with integer satisfaction and arbitrary real number prizes like doubles.

First the standard solution of the problem with integer prizes:

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]

This creates a table where the solution can be found by following the recursion for entry K[M, n].

Now the solution for the problem with real number weight:

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

The solution can now be found similiar to the other version. Instead of using the weight as first dimension we now use the total value of the items that lead to the minimal weight.
The code has more or less the same runtime O(S * N) whereas the other has O(M * N).

忆离笙 2025-01-03 05:49:20

您问题的答案取决于几个因素:

  1. 约束值有多大(如果缩放为斜线并转换为整数)。
  2. 有多少件物品。
  3. 要解决什么样的背包问题,
  4. 需要什么精度。

如果您有非常大的约束值(远超过数百万)和非常多的项目(远超过数千)

那么唯一的选择是贪心近似算法。按每单位重量价值的降序对物品进行排序,并按此顺序包装。

如果你想使用简单的算法并且不需要高精度

那么再次尝试使用贪心算法。 “满意度值”本身可能是非常粗略的近似值,那么当简单的近似值可能就足够了时,为什么还要费心发明复杂的解决方案呢?

如果您有非常大(甚至连续)的约束值,但项目数量非常少(少于数千)

,那么请使用分支定界方法。您不需要从头开始实施它。尝试GNU GLPK。它的分支剪切求解器并不完美,但可能足以解决小问题。

如果约束值和项目数量都很小

使用任何方法(DP、分支定界或只是暴力)。

如果约束值非常小(小于数百万)但项目太多(如数百万)

则 DP 算法是可能的。

最简单的情况是无界背包问题,即每种物品的副本数量没有上限。 这篇维基百科文章包含了如何简化问题的良好描述:UKP 中的支配关系以及如何解决它:无界背包问题

更困难的是0-1背包问题,当你只能打包每种物品零次或一次时。而有界背包问题,即允许将每种物品打包到一定的整数限制次数,则更加困难。互联网为这些问题提供了很多实现方案,同一篇文章中有一些建议。但我不知道哪一个是好是坏。

The answer to your question depends on several factors:

  1. How large is the value of constraint (if scaled to cants and converted to integers).
  2. How many items are there.
  3. What kind of knapsack problem is to be solved
  4. What is required precision.

If you have very large constraint value (much more than millions) and very many items (much more than thousands)

Then the only option is Greedy approximation algorithm. Sort the items in decreasing order of value per unit of weight and pack them in this order.

If you want to use a simple algorithm and do not require high precision

Then again try to use greedy algorithm. "Satisfaction value" itself may be very rough approximation, so why bother inventing complex solutions when simple approximation may be enough.

If you have very large (or even continuous) constraint value but pretty small number of items (less than thousands)

Then use branch and bound approach. You don't need to implement it from scratch. Try GNU GLPK. Its branch-and-cut solver is not perfect, but may be enough to solve small problems.

If both constraint value and number of items are small

Use any approach (DP, branch and bound, or just brute-force).

If constraint value is pretty small (less than millions) but there are too many (like millions) items

Then DP algorithms are possible.

Simplest case is the unbounded knapsack problem when there is no upper bound on the number of copies of each kind of item. This wikipedia article contains a good description how to simplify the problem: Dominance relations in the UKP and how to solve it: Unbounded knapsack problem.

More difficult is the 0-1 knapsack problem when you can pack each kind of item only zero times or one time. And the bounded knapsack problem, allowing to pack each kind of item up to some integer limit times is even more difficult. Internet offers lots of implementations for these problems, there are several suggestions in the same article. But I don't know which one is good or bad.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文