Solución óptima para la pregunta de la entrevista

Question

Recientemente en una entrevista de trabajo, me dieron el siguiente problema.

Decir que tengo la siguiente tabla

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
a     |   15.00   | 1 
b     |   30.00   | 1 
c     |   20.00   | 1 
d     |   25.00   | 1 

donde WIDGET_NAME se mantiene el nombre del widget, widget_costs es el precio de un widget, y en la acción es una constante de 1.

Ahora, para mi seguro comercial tengo un cierto deducible. Estoy buscando encontrar una declaración SQL que me diga cada widget y su precio excede el deducible. Así que si mi dedudctible es de $ 50.00 lo anterior solo regresarían

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
a     |   15.00   | 1 
d     |   25.00   | 1 

Desde widgets de B y C, donde se utiliza para satisfacer el deducible

Lo más cerca que pude conseguir es el siguiente

SELECT 
    * 
FROM (
    SELECT 
      widget_name, 
      widget_price 
    FROM interview.tbl_widgets 
    minus 
    SELECT widget_name,widget_price 
    FROM (
      SELECT 
       widget_name, 
       widget_price, 
       50 - sum(widget_price) over (ORDER BY widget_price ROWS between unbounded preceding and current row) as running_total 
      FROM interview.tbl_widgets 
    ) 
    where running_total >= 0 
) 
; 

cual da yo

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
c     |   20.00   | 1 
d     |   25.00   | 1 

porque utiliza a y b para cumplir con la mayoría de los deductibl e

Yo estaba esperando que alguien podría ser capaz de mostrar la respuesta correcta

EDIT: he entendido la pregunta de la entrevista a estar preguntando esto. Dada una tabla de widgets y sus precios y dado un monto en dólares, resta tantos widgets como puedas hasta el monto en dólares y devuelve esos widgets y sus precios que quedan

Answer 1

Esto parece un Bin Packing problem estos son muy difíciles de resolver, especialmente con SQL.

Si busca en SO para Bin Packing + SQL, encontrará how to find Sum(field) in condition ie “select * from table where sum(field) < 150” que es básicamente el mismo problema, excepto que desea agregar un NO EN.

no pude obtener la respuesta aceptada por brianegge a trabajar, pero lo que escribió sobre él en general era interesante

..el problema que describes de querer la selección de los usuarios lo que más se ajuste en un tamaño determinado, es un problema de embalaje bin. Este es un problema NP-Hard, y no se resolverá fácilmente con ANSI SQL. Sin embargo, lo anterior parece devolver el resultado correcto, pero de hecho simplemente comienza con el elemento más pequeño y continúa agregando elementos hasta el contenedor está lleno.

A, más eficaz algoritmo general de embalaje bin haría es empezar con el mayor en y continuar añadiendo más pequeños y cuando se ajusten. Este algoritmo seleccionaría usuarios 5 y 4.

Así que con este consejo se podría escribir un cursor para un bucle sobre la mesa para hacer precisamente esto (que simplemente no sería bastante).

Aaron Alton da un buen enlace a un series of articles que intenta resolver el problema de Bin Packing con sql pero básicamente concluye que probablemente sea mejor usar un cursor para hacerlo.

Answer 2

Voy a poner una respuesta, solo en caso es más fácil de lo que parece, pero si la idea es sólo para devolver cualquier widget que cuesta más que el deducible entonces usted haría algo como esto:

Select 
    Widget_Name, Widget_Cost, In_Stock 
From 
    Widgets 
Where 
    Widget_Cost > 50 -- SubSelect for variable deductibles? 

para sus datos de ejemplo mi consulta devuelve ninguna fila.

Answer 3

Creo que entiendo su pregunta, pero no soy 100%. Esto es lo que asumo que quiere decir:

Su deducible es, por ejemplo, $ 50. Para cumplir con el deducible tienes que "usar" dos elementos. (¿Esto siempre es dos? ¿Qué tan alto puede llegar? ¿Puede ser solo uno? ¿Qué pasa si no suman exactamente $ 50, hay mucha información faltante). A continuación, desea devolver los widgets que no son que se utilizan para deducible. Tengo lo siguiente.

CREATE TABLE #test 
(
    widget_name char(1), 
    widget_cost money 
    ) 

INSERT INTO #test (widget_name, widget_cost) 
SELECT 'a', 15.00 UNION ALL 
SELECT 'b', 30.00 UNION ALL 
SELECT 'c', 20.00 UNION ALL 
SELECT 'd', 25.00 


SELECT * FROM #test t1 
WHERE t1.widget_name NOT IN (
SELECT t1.widget_name FROM #test t1 
CROSS JOIN #test t2 
WHERE t1.widget_cost + t2.widget_cost = 50 AND t1.widget_name != t2.widget_name) 

que devuelve

widget_name widget_cost 
----------- --------------------- 
a   15.00 
d   25.00