blocks|key|251021|text|编辑:匈牙利算法不是你问题的答案，除非你不想限制供应商。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|251022|您要查找的算法是Hungarian+Algorithm。|offset|length|251023|在网络上有很多关于它的available+implementations。|251024|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Hungarian_algorithm|1|http://en.wikipedia.org/wiki/Hungarian_algorithm#Implementations^0|0|8|J|0|0|B|P|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

EDIT: Hungarian algorithm is not the answer to your question unless you did not wanted to put a limit on vendors.

The algorithm you are looking for is <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian Algorithm</a>.

There are many <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm#Implementations" rel="nofollow">available implementations</a> of it on the web.

blocks|key|2925520|text|使用贪婪的方法怎么样？因为你对供应商有限制(你至少需要使用v个供应商中的x个)。这意味着您需要从x的每个供应商中选择至少一种产品…下面是一个示例解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2925521|对于v中的每个供应商，按价格对产品进行排序，那么您将有"v“组排序的价格。现在，您可以选择这些集合中的最小值并再次排序，生成一个新的"v“产品集，其中只包含最便宜的产品。|2925522|现在，如果p+<=+v，那么选择前p个项目，你就完成了，否则选择所有v个项目，重复相同的逻辑，直到你达到p。|2925523|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

How about using a Greedy Approach. Since you have a limitation on the vendors ( you need to use at least x of the total v vendors). That means you need to choose at least 1 product from each vendor of the x ... And here's an example solution: 

For each vendor in v, sort the products by price, then you will have "v" sets of sorted prices. Now you can pick the min of these sets and sort again, producing a new set of "v" products, containing only the cheapest ones. 

Now, if p &lt;= v, then pick the first p items and you are done, otherwise pick all v items and repeat the same logic until you reach p.

blocks|key|246126|text|不正确，如@Per所示结构缺少最优子结构|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|246127|我的假设如下，在主表中，您需要创建一个只有"x“个供应商列的子列表，"Best+Price”是所有价格的"Sum“。|246128|使用动态编程方法，您要做的是定义两个函数：Picking+(i,k)和NotPicking(i,k)。它的意思是获得最好的能力，从1中选择供应商，..我最多有k个供应商。|CODE|246129|Picking+(1,_)+=+Sum(All+prices)
NotPicking+(1,_)+=+INF
Picking+(_,0)+=+INF
NotPicking+(_,0)+=+INF

Picking+(i,k)+=+Min+(Picking(i-1,k-1)+%2B+NotPicking(i-1,k-1))+-+D+(The+difference+you+get+because+of+having+this+vendor)
NotPicking+(i,k)+=+Min+(Picking(i-1,k)+%2B+NotPicking(i-1,k))|code-block|syntax|javascript|246130|你只需要解决从1到V的i和从1到X的k|246131|您可以通过维护每个挑选整个产品列表并计算差值来计算差值。|246132|entityMap^0|0|K|0|0|L|D|Z|F|0|0|B|1|I|1|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@$9|W|A|X|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Y|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|Z|8|@$9|10|A|11|B|J]|$9|12|A|13|B|J]]|D|@]|E|$]]|$1|K|3|L|5|M|7|14|8|@]|D|@]|E|$N|O]]|$1|P|3|Q|5|6|7|15|8|@$9|16|A|17|B|J]|$9|18|A|19|B|J]]|D|@]|E|$]]|$1|R|3|S|5|6|7|1A|8|@]|D|@]|E|$]]|$1|T|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|U|$]]

Not Correct as shown by @Per the structure lacks optimal substructure

My assumptions are as follows, from the master table you need to create a sub list which has only "x" vendor columns, and "Best Price" is the "Sum" of all the prices. 

Use a dynamic programming approach
What you do is define two functions, <code>Picking (i,k)</code> and <code>NotPicking(i,k)</code>.
What it means is getting the best with ability to pick vendors from 1,.. i with maximum of k vendors. 

<pre><code>Picking (1,_) = Sum(All prices)
NotPicking (1,_) = INF
Picking (_,0) = INF
NotPicking (_,0) = INF

Picking (i,k) = Min (Picking(i-1,k-1) + NotPicking(i-1,k-1)) - D (The difference you get because of having this vendor)
NotPicking (i,k) = Min (Picking(i-1,k) + NotPicking(i-1,k))
</code></pre>

You just solve it for a <code>i</code> from 1 to V and <code>k</code> from 1 to X

You calculate the difference by maintaining for each picking the whole product list, and calculating the difference.

blocks|key|246146|text|这个问题等价于非度量k-center+problem+(城市=产品，仓库=供应商)，这是NP难的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|246147|我会尝试混合整数编程。这里有一个公式。|246148|minimize+c(i,+j)+y(i,+j)++#+cost+of+all+of+the+orders
subject+to
for+all+i:+sum+over+j+of+y(i,+j)+=+1++#+buy+each+product+once
for+all+i,+j:+y(i,+j)+<=+z(j)++#+buy+products+only+from+chosen+vendors
sum+over+j+of+z(j)+<=+x++#+choose+at+most+x+vendors
for+all+i,+j:+0+<=+y(i,+j)+<=+1
for+all+j:+z(j)+in+{0,+1}|code-block|syntax|javascript|246149|变量的解释是i是产品，j是供应商，c(i,+j)是供应商j的产品i成本，如果我们从供应商j购买产品代码，y(i,+j)是1，否则<代码>D11i+>是<代码>D13是我们从供应商购买的<代码>D14，否则是<代码>D15。|style|CODE|246150|有many免费的混合整数程序求解器可用。|246151|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Metric_k-center|1|http://plato.asu.edu/ftp/milpf.html^0|A|G|0|0|0|0|6|1|B|1|H|7|S|1|W|1|18|1|1G|7|1O|1|0|1|4|1|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@$A|11|B|12|1|13]]|C|$]]|$1|D|3|E|5|6|7|14|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|15|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|16|8|@$A|17|B|18|M|N]|$A|19|B|1A|M|N]|$A|1B|B|1C|M|N]|$A|1D|B|1E|M|N]|$A|1F|B|1G|M|N]|$A|1H|B|1I|M|N]|$A|1J|B|1K|M|N]|$A|1L|B|1M|M|N]]|9|@]|C|$]]|$1|O|3|P|5|6|7|1N|8|@]|9|@$A|1O|B|1P|1|1Q]]|C|$]]|$1|Q|3|-4|5|6|7|1R|8|@]|9|@]|C|$]]]|R|$S|$5|T|U|V|C|$W|X]]|Y|$5|T|U|V|C|$W|Z]]]]

This problem is equivalent to the non-metric <a href="http://en.wikipedia.org/wiki/Metric_k-center" rel="nofollow">k-center problem</a> (cities = products, warehouses = vendors), which is NP-hard.

I would try mixed integer programming. Here's one formulation.

<pre><code>minimize c(i, j) y(i, j) # cost of all of the orders
subject to
for all i: sum over j of y(i, j) = 1 # buy each product once
for all i, j: y(i, j) &lt;= z(j) # buy products only from chosen vendors
sum over j of z(j) &lt;= x # choose at most x vendors
for all i, j: 0 &lt;= y(i, j) &lt;= 1
for all j: z(j) in {0, 1}
</code></pre>

The interpretation of the variables is that <code>i</code> is a product, <code>j</code> is a vendor, <code>c(i, j)</code> is the cost of product <code>i</code> from vendor <code>j</code>, <code>y(i, j)</code> is <code>1</code> if we buy product <code>i</code> from vendor <code>j</code> and <code>0</code> otherwise, <code>z(j)</code> is <code>1</code> is we buy from vendor <code>j</code> at all and <code>0</code> otherwise.

There are <a href="http://plato.asu.edu/ftp/milpf.html" rel="nofollow">many</a> free mixed integer program solvers available.

blocks|key|248105|text|我还没有解决这个问题并进行验证，但我猜它可能会起作用。试试这个：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|248106|向表中添加另外两个名为“最高价格”和“最低价格”的列，并为其生成数据:它们应该包含所有供应商中每种产品的最高和最低价格。还要添加另一列，名为"Range“，它应该包含(最高价格-最低价格)。|248107|现在这样做100+(p)次：|248108|248109|选择范围最大的行。买那一排价格最低的产品。购买后，将该单元格标记为“已购买”(可能为该行设置null).|ordered-list-item|248110|Recalculate最低价格、范围(忽略标记为“已购买”的单元格)。|248111|248112|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]|$1|G|3|H|5|I|7|S|8|@]|9|@]|A|$]]|$1|J|3|K|5|I|7|T|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|N|$]]

I haven't worked this out and verified, but I guess it might work. Try this: 

Add two more columns called "Highest Price" and "Lowest Price" to the table and generate data for it: they should hold the highest and lowest price for each product amongst all vendors.
Also add another column, called "Range" which should hold the (highest price - lowest price).

Now do this 100 (p) times:

<ol>
<li>Pick the row with highest range. Buy the product with least price on
that row. Once bought, mark that cell as 'bought' (maybe set null).</li>
<li>Recalculate lowest price, range for that row (ignoring cells marked as 'bought').</li>
</ol>

I have to buy 100 Products ( or p Products) from 20 Vendors ( or v Vendors). Each Vendors have all of these Products, but they sell different Price. 

<img src="https://i.stack.imgur.com/fdlUU.jpg" alt="http://i.stack.imgur.com/oaupb.jpg &lt;&lt; Image description. Sorry, I can not post Image because I&#39;m a new user.">

I want to find the best price to get 100 Products. Asume that there is no Shipping Cost.
There are v^p ways. And I will get only one way that have best Price.
The problem seem to be easy if there is no requirement: LIMIT number of Vendors to x in the Orders because of Time Delivery ( or Some reasons).

So, the problem is: Find the best way to buy p Product from limit x Vendors ( There are v Vendors , x&lt;=v).

I can generate all Combination of Vendors( There are C(v,x) combinations) and compare the Total Price. But There are so many combinations . (if there are 20 Vendors, there are around 185k combinations).
I stuck at this idea. 
Someone has same problem , pls help me. Thank you very much.

Find the best way to buy p Product from limit x Vendors

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

I必须从20个供应商(或v个供应商)购买 100产品(或p产品)。每个供应商都有所有这些产品，但他们销售不同的价格。​​我想找到最好的价格得到100个产品。Asume没有运费。有v^p种方法。我只会得到一个方法，有最好的价格。如果没有要求，问题似乎很简单:由于交货时间(或某些原因)，将订单中的供应商数量限制在x。因此，...

问找到从limit x供应商那里购买p产品的最佳方式
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到从limit x供应商那里购买p产品的最佳方式EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到从limit x供应商那里购买p产品的最佳方式
EN