Sınırlandırılmış girişi olası çıktılarla eşleşen bir algoritma var mı?

Question

Bir kullanıcının farklı son ürünlere dönüştürülebilecek giriş ürünlerinin bir listesini sunduğu bir sorun üzerinde çalışıyorum. Her bir girdi ürününün, üretilebilecek belirli bir çıktı grubu vardır. Kullanıcı ayrıca beklenen çıktı ürünlerinin bir listesini ve her birinin ne kadarını istediğini sağlar. Mümkün olan en uygun şekilde talebi karşılamak için çıktılara çeşitli girdileri eşleştirmek için bilinen bir algoritma olup olmadığını görmek istiyorum.

Örnek:

A Ürünü ürünleri X haline gelebilir ve Y
Ürün B 3 X 5 A ve 7 B.
var yapabilir edilir Y ve Z

ürünler haline gelebilir, 4 Y ve 6 Z?

bana çıktı bulmasına yardımcı olacak bir yaklaşım istiyorum:

3 A -> X
2 A -> Y
2 B -> Y
5 B -> Z
Sen olarak inşa akış ağa max flow algorithms herhangi uygulayarak bu sorunu çözebilir Z

Answer 1

1 Eksik aşağıdaki gibidir:

• kaynak düğüm S ekleyin ve lavabo düğümü T
• her giriş bir ürün için ilave düğüm bir _i
• her çıkış ürünü için her bir giriş ürünü için düğüm Z _j
• ekleme ile S'den bir kenar eklemek her çıkış ürünü için, karşılık gelen bir ürün
• sayısına eşit kapasitesi karşılık gelen ürün, arzu edilen sayıda, her bir _ikaynaktan
• eşit kapasiteli T bir kenar eklemekve Z _j A _i ürünün İşte

ağı örneğin nasıl görüneceğini olduğunu sayısına eşit kapasiteli bir kenar ekleyin. Maksimum akım T giren toplam kapasitesi eşitse

, bir çözelti, dakika kedi tarafından tanımlanır; Aksi takdirde, bir çözüm mümkün değildir.

Not: tek ihtiyacınız bir evet/hayır cevabı ise, A _i düğümleri kaldırabilir, bu çıkış için toplam eşit kapasitelerde, Z _j için S'den kenarları eklemek yerinden girdi ürünleri (yani X = 5, Y = 12 ve Z = 7). Bu, aynı karar sonucunu üretecektir, ancak süreçte her bir türden kaç tane girdi ürününün tüketilmesi gerektiğini öğrenemezdiniz.