Verilen 2 diziler, iki dizinin <code>A</code> ve <code>B</code>, her biri <code>n</code> olmayan negatif sayılar göz önüne alındığında ürünler

Question

minimum toplamı bulunur B. ucundan bir ucundan a>0 elemanları ve b>0 elemanları uzaklaştırmak X*Y gibi bir işlemin maliyetini, X'unve Y öğelerinden kaldırılan a öğelerinin toplamı B'dan kaldırılan b öğelerinin toplamı olduğunu değerlendirin. Her iki dizi de boş olana kadar bunu yapmaya devam edin. Amaç toplam maliyeti en aza indirmektir.

Dinamik programlamayı ve en uygun stratejinin her zaman A veya B öğelerinden birini alması gerçeğini kullanarak bir O (n^3) çözümü bulabilirim. Şimdi bu problem için daha hızlı bir çözüm olup olmadığını merak ediyorum.

DÜZENLEME: açıklamalarda @recursive bir örnek çalma:

A = [1,9,1] ve B = [1, 9, 1]. 20 katlık bir maliyetle yapmak mümkün (1) * (1 + 9) + (9 + 1) * (1)

Answer 1

İşte O(n^2) bu. CostA(i, j), A[1..i], B[1..j]'u ortadan kaldırmanın en düşük maliyeti olacak, böylece ilk kaldırma işlemi B'dan sadece bir öğe alacaktır. CostB(i, j)'un, A[1..i], B[1..j]'u ortadan kaldırmanın en düşük maliyeti olmasına izin verin, böylece ilk kaldırma işlemi A'dan yalnızca bir öğe alır. Biz karşılıklı özyinelemeli rekürenslerini baz durumlarda

CostA(0, 0) = 0 
CostA(>0, 0) = infinity 
CostA(0, >0) = infinity 
CostB(0, 0) = 0 
CostB(>0, 0) = infinity 
CostB(0, >0) = infinity. 

cevap min(CostA(n, n), CostB(n, n)) olduğu ile

CostA(i, j) = A[i] * B[j] + min(CostA(i - 1, j), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 
CostB(i, j) = A[i] * B[j] + min(CostB(i, j - 1), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 

var.