Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
---Справочник продукции с весом
DECLARE @Lot as table(LotID int ,Weight int)

INSERT INTO @Lot(LotID,Weight)
VALUES
      (1,10),
      (2,55),
      (3,30),
      (4,50)
--Заявки на приобретение покупателем лота по определенной цене
DECLARE @Request as table(CustomerID int,LotID int ,Price int)
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES
            (1,1,1),
            (2,1,3),
            (3,2,1),
            (3,4,2),
            (4,3,10);
 

 ---Продать лот по наивыгоднейшей цене
 with CTE_Sale
 as
 (
 SELECT CustomerID,LotID,ROW_NUMBER()over(partition by LotID order by Price desc,CustomerID) PriceOrder
    FROM @Request R
  )

  SELECT  CustomerID,S.LotID,L.Weight,SUM(L.Weight) over (partition by CustomerID) 'Load' --загруженность покупателя
  FROM CTE_Sale S inner join @Lot L on L.LotID=S.LotID
  WHERE S.PriceOrder=1




CustomerID LotID Weight Load
----------- ----------- ----------- -----------
|2 |1 | 10 |10
|3 |2 |55 |105
|3 |4 |50 |105
|4 |3 |30 |30
----------- ----------- ----------- -----------
--Появилось новое требование чтоб покупатель не перегружался больше 100

Очень похоже что свелась к классической задаче про ранец http://ru.wikipedia.org/wiki/Задача_о_ранце
Подскажите, пожалуйста, как можно удовлетворить этому требованию.
Спасибо
30 май 13, 15:29    [14370911]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Glory
Member

Откуда:
Сообщений: 104751
Wisky
Появилось новое требование чтоб покупатель не перегружался больше 100

Просто больше 100 ? Или с наибольшим количеством лотов не больше 100 ? Или с наибольшим количеством лотов не больше 100 с максмальными Load при равном количестве лотов ?
30 май 13, 16:02    [14371167]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
При наиболее выгодной суммарной выручке с продаж, не перегрузить покупателя

  SELECT  CustomerID,S.LotID,L.Weight,SUM(L.Weight) over (partition by CustomerID) 'Load'--загруженность покупателя
  ,SUM(S.Price) over() --общая выгода 
  ,S.Price -- за что продали лот
  FROM CTE_Sale S inner join @Lot L on L.LotID=S.LotID
  WHERE S.PriceOrder=1
30 май 13, 16:28    [14371372]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
Load каждого Customer'a не может быть больше 100
30 май 13, 16:33    [14371420]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
ROLpogo
Member

Откуда: Реутов
Сообщений: 219
Wisky,

select
  CustomerID, LotID, Weight, Load
from(
  select
    R.CustomerID,
    R.LotID,
    L.Weight,
    sum(L.Weight) over(partition by R.CustomerID) as Load,
    row_number() over(partition by L.LotID order by R.Price desc, R.CustomerID) PriceOrder
  from @Request R
    inner join @Lot L on L.LotID = R.LotID) t
where PriceOrder = 1 and Load <= 100
30 май 13, 23:47    [14373023]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
ROLpogo,
так вы не продали вещи только из-за того, что богатый клиент не смог их унести, хотя их хотел кто еще другой покупатель
31 май 13, 09:33    [14373718]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
ambarka_max
Member

Откуда: Россия
Сообщений: 517
Нужно вводить дополнительный приоритет. Или расширять термин "продать по наивыгоднейшей цене" который означает "наивыгоднейшая цена собранного рюкзака". Но тогда для покупателей лот будет непрозрачным.
31 май 13, 10:01    [14373879]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
ambarka_max,
"продать по наивыгоднейшей цене" - это значит наивысшая суммарная стоимость всех рюкзаков (лотов проданных одному покупателю), в случае если таких вариантов несколько то устраивает любой
31 май 13, 11:42    [14374565]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
ROLpogo
Member

Откуда: Реутов
Сообщений: 219
Wisky,

Для большего понимания условия, лучше его сформулировать так:
Условие задачи:
Выдать сводную таблицу продаж лотов покупателям с учетом получения максимальной прибыли от продаж и ограничением на вес, который может унести один покупатель.
31 май 13, 12:28    [14375011]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
ROLpogo,
Спасибо, лаконичнее не сказала бы ))
31 май 13, 12:49    [14375178]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
матрица возможных вариантов для данных этого конкретного примера, отсортированная по уменьшению выручки (поле PRICE):
l1c1p1w1l2c2p2w2l3c3p3w3l4c4p4w4pricewc1wc2wc3wc4
1231023155341030432501601010530
12310200034103043250150105030
1111023155341030432501410010530
12310231553410304000140105530
10002315534103043250130010530
11110200034103043250131005030
123102000341030400013010030
100020003410304325012005030
11110231553410304000121005530
100023155341030400011005530
111102000341030400011100030
1000200034103040001000030
123102315530004325060101050
1231020003000432505010500
111102315530004325041001050
1231023155300040004010550
1000231553000432503001050
1111020003000432503100500
12310200030004000301000
10002000300043250200500
1111023155300040002100550
10002315530004000100550
11110200030004000110000
100020003000400000000
При этом в полях WC1,...WC4 вес, набранный соответственно покупателями 1,2,3 и 4

расшифровка матрицы:
l1 - лот №1, c1 - кому продан (ид покупателя), p1 - выручка за лот 1 от выбранного покупателя, w1 - вес первого лота
если c1=0 - лот №1 никому не продан
остальные поля аналогичны
+ частный случай решения, строящий полученную матрицу
---Справочник продукции с весом
DECLARE @Lot as table(LotID int ,Weight int)

INSERT INTO @Lot(LotID,Weight)
VALUES
      (1,10),
      (2,55),
      (3,30),
      (4,50)
--Заявки на приобретение покупателем лота по определенной цене
DECLARE @Request as table(CustomerID int,LotID int ,Price int)
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES
            (1,1,1),
            (2,1,3),
            (3,2,1),
            (3,4,2),
            (4,3,10);

with cte as(
   select 1 step, 0 pl, 0 pc, 1 lot, r.CustomerID, l.Weight, r.Price
      FROM @Lot l 
      join @Request r on r.LotID=l.LotID
      where l.LotID=1
      union all select 1,0,0,1,0,0,0
   union all
   select c.step+1,c.lot, c.CustomerID,l.LotID, r.CustomerID, l.Weight, r.Price
      from cte c
      join @Lot l on l.LotID=c.lot+1
      join @Request r on r.LotID=l.LotID
      union all 
      select c.step+1,c.lot, c.CustomerID,l.LotID,0,0,0
         from cte c
         join @Lot l on l.LotID=c.lot+1
   ),
vars as (
   select 
      ROW_NUMBER()over(order by c1.lot,c1.CustomerID,c2.lot,c2.CustomerID,c3.lot,c3.CustomerID,c4.lot,c4.CustomerID)rn,
      c1.lot l1,c1.CustomerID c1,c1.Price p1,c1.Weight w1,
      c2.lot l2,c2.CustomerID c2,c2.Price p2,c2.Weight w2,
      c3.lot l3,c3.CustomerID c3,c3.Price p3,c3.Weight w3,
      c4.lot l4,c4.CustomerID c4,c4.Price p4,c4.Weight w4,
      c1.Price+c2.Price+c3.Price+c4.Price price,
      wc.*
   from cte c1
   join cte c2 on c2.step=2 and c2.pl=c1.lot and c2.pc=c1.CustomerID
   join cte c3 on c3.step=3 and c3.pl=c2.lot and c3.pc=c2.CustomerID
   join cte c4 on c4.step=4 and c4.pl=c3.lot and c4.pc=c3.CustomerID
   cross apply (select 
      case c1.CustomerID when 1 then c1.Weight else 0 end +
      case c2.CustomerID when 1 then c2.Weight else 0 end +
      case c3.CustomerID when 1 then c3.Weight else 0 end +
      case c4.CustomerID when 1 then c4.Weight else 0 end wc1,
      case c1.CustomerID when 2 then c1.Weight else 0 end +
      case c2.CustomerID when 2 then c2.Weight else 0 end +
      case c3.CustomerID when 2 then c3.Weight else 0 end +
      case c4.CustomerID when 2 then c4.Weight else 0 end wc2,
      case c1.CustomerID when 3 then c1.Weight else 0 end +
      case c2.CustomerID when 3 then c2.Weight else 0 end +
      case c3.CustomerID when 3 then c3.Weight else 0 end +
      case c4.CustomerID when 3 then c4.Weight else 0 end wc3,
      case c1.CustomerID when 4 then c1.Weight else 0 end +
      case c2.CustomerID when 4 then c2.Weight else 0 end +
      case c3.CustomerID when 4 then c3.Weight else 0 end +
      case c4.CustomerID when 4 then c4.Weight else 0 end wc4
      ) wc
   where c1.step=1 
   )
select distinct --top (1) with ties 
   l1, c1, p1, w1, l2, c2, p2, w2, l3, c3, p3, w3, l4, c4, p4, w4, price, wc1, wc2, wc3, wc4
   from vars
--where wc1<=100 and wc2<=100 and wc3<=100 and wc4<=100
order by price desc
31 май 13, 13:20    [14375435]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
))
31 май 13, 15:19    [14376352]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
динамика не прокатит
3 июн 13, 10:10    [14382180]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
---Справочник продукции с весом
DECLARE @Lot as table(LotID int ,Weight int)

INSERT INTO @Lot(LotID,Weight)
VALUES
      (1,10),
      (2,55),
      (3,30),
      (4,50),
      (5,55),
      (6,50)
--Заявки на приобретение покупателем лота по определенной цене
DECLARE @Request as table(RequestID int identity(1,1) primary key, CustomerID int,LotID int ,Price int)
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES      (1,1,1),
            (1,2,1),
            (1,3,1),
            (1,4,1),
            (1,5,1),
            (1,6,1),
            (2,1,3),
            (2,2,3),
            (2,3,3),
            (3,2,1),
            (4,3,2),
            (5,4,10),
            (6,5,11);
 

 

declare @deep int=1
declare @hash as table(AllLots varchar(max),Path varchar(max), deep int,LastRequestID int);



insert into @hash(AllLots,Path,deep,LastRequestID)
select  '|'+cast(C.LotID as varchar(max))+'|' AllLots,
        '<Request><CustomerID>'+cast(C.CustomerID as varchar(max))+'</CustomerID><LotID>'+cast(C.LotID as varchar(max))+'</LotID></Request>'  Path,
        @deep deep,
        C.RequestID LastRequestID
from @Request C inner join @Lot L on L.LotID=C.LotID



while 1=1
begin
    set @deep=@deep+1

insert into @hash(AllLots,Path,deep,LastRequestID)    
    select cte.AllLots+cast(R.LotID as varchar(max))+'|',
        cte.Path+'<Request><CustomerID>'+cast(R.CustomerID as varchar(max))+'</CustomerID><LotID>'+cast(R.LotID as varchar(max))+'</LotID></Request>'  Path,
        cte.deep+1 deep,
        R.RequestID LastRequestID
    from  @hash cte inner join @Request R on cte.AllLots not like '%|'+cast(R.LotID as varchar(max))+'|%' and R.RequestID>cte.LastRequestID and cte.deep=@deep-1
if @@ROWCOUNT=0 break
end    

select cast(H.Path as xml)
from @hash H


Подскажите плиз как insert формирующий новую версию добавить проверку на перегруз покупателя, чтоб не рассматривать ветви с заведомым перебором?
4 июн 13, 15:10    [14389419]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
declare @hash as table(id int identity(1,1),x xml)

insert into @hash(x)
values(
'<Request CustomerID="1" LotID="1" />
<Request CustomerID="1" LotID="2" />
<Request CustomerID="2" LotID="3" />'
)

DECLARE @Customer as table(CustomerID int)
INSERT INTO @Customer(CustomerID)
VALUES
(1),
(2),
(3)


select t.id,z.value('@CustomerID','int') as CustomerID,z.value('@LotID','int') as LotID
from @hash t
outer apply
t.x.nodes('/Request') z ( z )

id CustomerID LotID
----------- ----------- -----------
1 1 1
1 1 2
1 2 3
1 3 NULL (как добавить не хватающего покупателя)
5 июн 13, 15:28    [14395263]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Илья Петров
Member

Откуда:
Сообщений: 43
with res( lotId, CustomerId, Amount, rn) as
( select lotId, CustomerId, sum(price) over (partition by rn), rn from
(select lotId, CustomerID, Price, rn,
sum(Weight) over(partition by rn, CustomerId) ClientWeight
from
(
select r.LotID, r.CustomerID, r.Price, ROW_NUMBER() over (partition by r.LotId order by r.CustomerId ) rn, l.Weight
from @Request r inner join @Lot l on r.LotID = l.LotID) q
) x where ClientWeight <=100)
select lotId, CustomerId from res a
where rn = (select min(rn) from res b where amount = (select max(amount) from res c))
6 июн 13, 11:15    [14398632]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
Илья Петров,
Спасибо большое, но если заменить
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES
            (1,1,1),

на
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES
            (1,1,100),


лот№1 все равно достается CustomerId=2
6 июн 13, 16:01    [14400674]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
Сделала кое как, только как то это все рационализировать надо, уж ОЧЕНЬ УБОГО выглядит

---Справочник продукции с весом
DECLARE @Lot as table(LotID int ,Weight int)
DECLARE @Customer as table(CustomerID int)
INSERT INTO @Lot(LotID,Weight)
VALUES    (0,0),
      (1,10),
      (2,55),
      (3,30),
      (4,50),
      (5,55),
      (6,50)
--Заявки на приобретение покупателем лота по определенной цене
DECLARE @Request as table(RequestID int identity(1,1) primary key, CustomerID int,LotID int ,Price int)
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES      (1,1,100),
            (1,2,1),
            (1,3,1),
            (1,4,1),
            (1,5,1),
            (1,6,1),
            (2,1,3),
            (2,2,3),
            (2,3,3),
            (3,2,1),
            (4,3,2),
            (5,4,10),
            (6,5,11);
 


 insert into @Customer
 select distinct CustomerID
 from @Request
 
declare @deep int=1
declare @hash as table(AllLots varchar(max),Path xml, deep int,LastRequestID int,cost int);



insert into @hash(AllLots,Path,deep,LastRequestID,cost)
select  '|'+cast(C.LotID as varchar(max))+'|' AllLots,
        '<Request CustomerID="'+cast(C.CustomerID as varchar(max))+'" LotID="'+cast(C.LotID as varchar(max))+'"></Request>'  Path,
        @deep deep,
        C.RequestID LastRequestID,
        C.Price
from @Request C inner join @Lot L on L.LotID=C.LotID

declare @R varchar(max)=''
update @Customer set @R=@R++'<Request CustomerID="'+cast(CustomerID as varchar(max))+'" LotID="'+cast(0 as varchar(max))+'"></Request>'
 
update U
set path=cast(path as varchar(max))+@R
from @hash U



while 1=1
begin
    set @deep=@deep+1

insert into @hash(AllLots,Path,deep,LastRequestID,cost)    
    select cte.AllLots+cast(R.LotID as varchar(max))+'|',
        cast(cte.Path as varchar(max))+'<Request CustomerID="'+cast(R.CustomerID as varchar(max))+'" LotID="'+cast(R.LotID as varchar(max))+'"></Request>'  Path,
        @deep deep,
        R.RequestID LastRequestID,
        cte.cost+R.Price cost
    from  
    
    
(

select CustomerID,cast(Path as varchar(max)) Path,Sum(L.Weight) Sum,A.AllLots,A.LastRequestID,A.cost
from 
((select t.path,z.value('@CustomerID','int') as CustomerID,z.value('@LotID','int') as LotID,AllLots,LastRequestID,t.cost
from   @hash  t
cross apply    
       t.Path.nodes('/Request') z ( z )

where t.deep=@deep-1
) A  join @Lot L on  A.LotID=L.LotID)
    
group by CustomerID,cast(Path as varchar(max)),AllLots,LastRequestID,cost
)
    
    
    cte inner join @Request R inner join @Lot L on L.LotID=R.LotID on cte.AllLots not like '%|'+cast(R.LotID as varchar(max))+'|%' 
    and R.RequestID>cte.LastRequestID and cte.CustomerID=R.CustomerID and cte.Sum+L.Weight<=100
if @@ROWCOUNT=0 break
end    

select 
top(1) WITH TIES 
z.value('@CustomerID','int') as CustomerID,z.value('@LotID','int') as LotID,L.Weight,t.cost,sum(L.Weight)  over(partition by z.value('@CustomerID','int') ,cast(t.path as varchar(max))) CustomerWeight
from @hash  t
cross apply    
       t.Path.nodes('/Request') z ( z ) inner join @Lot L on L.LotID=z.value('@LotID','int') 
where z.value('@LotID','int')!=0
order by t.cost desc,cast(t.path as varchar(max))
6 июн 13, 17:27    [14401387]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
не нравится бесполезный
group by CustomerID,cast(Path as varchar(max)),AllLots,LastRequestID,cost

по лишним полям и
declare @R varchar(max)=''
update @Customer set @R=@R+'<Request CustomerID="'+cast(CustomerID as varchar(max))+'" LotID="'+cast(0 as varchar(max))+'"></Request>'
 
update U
set path=cast(path as varchar(max))+@R
from @hash U

раздувание стартовых версий
7 июн 13, 10:21    [14404237]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
ужасно нерационально получается, может у кого есть идеи по самому алгоритму?
17 июн 13, 15:24    [14442713]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
у кого есть желание поиграть в оптимизацию, приложила скриптик, сама надежду уже потеряла.

К сообщению приложен файл (ранец2.sql - 7Kb) cкачать
17 июн 13, 15:50    [14442974]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
ROLpogo
Member

Откуда: Реутов
Сообщений: 219
Wisky,

Вот вариант решения с условием поста [14401387]. Решение найдено за 8 сек. Алгоритм рассчитан на кол-во заявок, не превышающих 64. При большем количестве уже нужно подключать генетический алгоритм.

+
set nocount on

---Справочник продукции с весом
if OBJECT_ID('Lot', 'U') is null
begin
  create table Lot
  (
    LotID  int,
    Weight int
  ) on [primary]
end
go

if not exists(select 1 from Lot)
  insert into Lot(LotID, Weight)
  values(1,10),
        (2,55),
        (3,30),
        (4,50),
        (5,55),
        (6,50)

--Заявки на приобретение покупателем лота по определенной цене
if OBJECT_ID('Request', 'U') is null
begin
  create table Request
  (
    RequestID int identity(1,1) primary key,
    CustomerID int,
    LotID      int,
    Price      int
  ) on [primary]
end
go

if not exists(select 1 from Request)
  insert into Request(CustomerID,LotID,Price)
  values      (1,1,100),
              (1,2,1),
              (1,3,1),
              (1,4,1),
              (1,5,1),
              (1,6,1),
              (2,1,3),
              (2,2,3),
              (2,3,3),
              (3,2,1),
              (4,3,2),
              (5,4,10),
              (6,5,11)

-- алгоритм поиска сводной таблицы продаж лотов покупателям с учетом получения максимальной прибыли от продаж и ограничением на вес, который может унести один покупатель.
-- Прмечание: алгоритм работает с кол-вом заявок < 65

-- сводная таблица заявок с весом и промаскированными строками.
create table #Src
(
  RowMask    bigint,
  RequestID  int,
  CustomerID int,
  LotID      int,
  Price      int,
  Weight     int
)
-- сюда будем заливать очередную генерацию
create table #Populate
(
  CustomerID    int,
  Price         int,
  Weight        int,
  TwilightCount int
)
-- сюда отсеиваем лучшую по стоимости генерацию
create table #BestChoice
(
  Mask     bigint,
  SumPrice int,
)

insert into #BestChoice(Mask, SumPrice) values(0, 0)

insert into #Src
  select
    power(2, row_number() over (order by R.RequestID) - 1),
    R.RequestID,
    R.CustomerID,
    L.LotID,
    R.Price,
    L.Weight
  from Request R
    inner join Lot L on L.LotID = R.LotID

select
  RequestID, CustomerID, LotID, Price, Weight
from #Src
order by LotID

declare @RowCount int,
        @Mask     bigint,
        @SumPrice int

select  @RowCount = count(*) from #Src
select  @Mask     = power(2, cast(@RowCount as float)) - 1

while @Mask > 0
begin
  truncate table #Populate
  insert into #Populate
    select
      CustomerID,
      Price,
      Weight,
      count(*) over (partition by LotID) as TwilightCount
    from #Src
    where RowMask & @Mask != 0
    group by
      RequestID,
      LotID,
      CustomerID,
      Price,
      Weight

  if not exists(select 1 from #Populate where TwilightCount > 1) and                    -- если в популяции нет задвоенных лотов
     not exists(select 1 from #Populate group by CustomerID having sum(Weight) > 100)   -- и нет превышения по весу для покупателей, то рассмотрим этого кандидата.
  begin
    select @SumPrice = sum(Price) from #Populate

    if exists (select 1 from #BestChoice where SumPrice < @SumPrice)
    begin
      truncate table #BestChoice
      insert into #BestChoice select @Mask, @SumPrice
    end
  end

  set @Mask = @Mask - 1
end

select
  RequestID, CustomerID, LotID, Price, Weight
from #Src
where RowMask & (select top 1 Mask from #BestChoice) != 0
order by LotID

select SumPrice from #BestChoice

drop table #Src
drop table #Populate
drop table #BestChoice

set nocount off


RequestID   CustomerID  LotID       Price       Weight
----------- ----------- ----------- ----------- -----------
1 1 1 100 10
7 2 1 3 10
8 2 2 3 55
2 1 2 1 55
10 3 2 1 55
11 4 3 2 30
3 1 3 1 30
9 2 3 3 30
4 1 4 1 50
12 5 4 10 50
13 6 5 11 55
5 1 5 1 55
6 1 6 1 50

RequestID CustomerID LotID Price Weight
----------- ----------- ----------- ----------- -----------
1 1 1 100 10
8 2 2 3 55
9 2 3 3 30
12 5 4 10 50
13 6 5 11 55
6 1 6 1 50

SumPrice
-----------
128
18 июн 13, 13:05    [14447384]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
+ еще вариант полного решения задачи
---Справочник продукции с весом
DECLARE @Lot as table(LotID int ,Weight int)
INSERT INTO @Lot(LotID,Weight)
VALUES  (1,10),(2,55),(3,30),(4,50),(5,55),(6,50)

-- учесть максимально допустимый вес
declare @MaxWeight int = 80

---Справочник покупателей
--DECLARE @Customer as table(CustomerID int)
--insert @Customer values(1),(2),(3),(4),(5),(6)


--Заявки на приобретение покупателем лота по определенной цене
DECLARE @Request as table(RequestID int identity(1,1) primary key, CustomerID int,LotID int ,Price int)
INSERT INTO @Request(CustomerID,LotID,Price)
VALUES  
   (1,1,100),(1,2,1),(1,3,1),(1,4,1),(1,5,1),(1,6,1),
   (2,1,3),(2,2,3),(2,3,3),
   (3,2,1),
   (4,3,2),
   (5,4,10),
   (6,5,11);
   
-- включение в список заявок вариантов отказа от покупки для каждого лота
insert @Request (CustomerID,LotID,Price) 
   select 0,l.LotID,0 
   from @Lot l;

-- формирование списка вариантов продаж
with 
renum as ( -- сформировать очередность выставления лотов на аукцион
   select 
      ROW_NUMBER()over(order by l.LotID) stage,
      l.LotID, l.Weight
   from @Lot l
   ),
vars as( -- все варианты торгов по лотам
   select 
         l.stage, -- номер этапа торгов (порядковый номер выставленного на продажу лота)
         0 prev_LotID, 0 prev_CustomerID, -- результаты предыдущего этапа торгов (кому был продан предыдущий лот)
         l.LotID, r.CustomerID, -- результаты данного этапа торгов (кому продается представленный лот)
         CONVERT(varchar(max),
            '<v>'+
            '<l>'+CONVERT(varchar(100),l.LotID)+'</l>'+ 
            '<c>'+CONVERT(varchar(100),r.CustomerID)+'</c>'+
            '<w>'+CONVERT(varchar(100),case when r.CustomerID=0 then 0 else l.Weight end)+'</w>'+
            '<p>'+CONVERT(varchar(100),r.Price)+'</p>'+
            '</v>') vars, -- история варианта торгов
         r.Price sumPrice -- стоимость по выбранному варианту торгов
      from renum l
      join @Request r on r.LotID=l.LotID
      where l.stage=1
   union all
   select
         l.stage,
         v.LotID, v.CustomerID, 
         l.LotID, r.CustomerID, 
         CONVERT(varchar(max),v.vars+
            '<v>'+
            '<l>'+CONVERT(varchar(100),l.LotID)+'</l>'+ 
            '<c>'+CONVERT(varchar(100),r.CustomerID)+'</c>'+
            '<w>'+CONVERT(varchar(100),case when r.CustomerID=0 then 0 else l.Weight end)+'</w>'+
            '<p>'+CONVERT(varchar(100),r.Price)+'</p>'+
            '</v>') vars, -- история варианта торгов
         v.sumPrice+r.Price
      from vars v
      join renum l on l.stage=v.stage+1
      join @Request r on r.LotID=l.LotID
   )
select 
   rez.VariantID, 
   x.i.value('./l[1]','int')LotId, 
   x.i.value('./c[1]','int')CustomerId, 
   x.i.value('./p[1]','int')Price, 
   x.i.value('./w[1]','int')Weight,
   rez.sumPrice, rez.MaxWeight
from (
   select top (1) with ties 
      ROW_NUMBER()over(order by (select 0)) VariantID,
      vars, sumPrice, max(sumWeight)MaxWeight
   from ( -- развернуть строки вариантов по весу
      select 
         v.vars, sumPrice,  
         sum(x.i.value('./w[1]','int'))over(partition by v.vars, x.i.value('./c[1]','int')) sumWeight
      from vars v
      cross apply (select convert(xml,v.vars) xml_vars) c
      cross apply xml_vars.nodes('/v') x(i)
      where v.stage=(select COUNT(*) from @Lot)
      ) x
   group by vars, sumPrice
   having max(sumWeight) <= @MaxWeight -- отклонить варианты с превышением веса
   order by sumPrice desc
   ) rez
cross apply (select CONVERT(xml,rez.vars) xml_vars ) c
cross apply xml_vars.nodes('/v') x(i)
order by rez.VariantID, x.i.value('./l[1]','int')
VariantIDLotIdCustomerIdPriceWeightsumPriceMaxWeight
396111001012760
3962235512760
3963423012760
39645105012760
39656115512760
3966115012760
18 июн 13, 16:21    [14449037]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
ROLpogo
Member

Откуда: Реутов
Сообщений: 219
Алгоритм можно ещё соптимизировать, убрав из цикла заявки с лотами, которые захотел купить единственный покупатель, и подавший единственную заявку. Тогда предел заявок для алгоритма может быть увеличен за счет этих отброшенных записей. (В данном примере таких заявок не оказалось.)
18 июн 13, 16:21    [14449039]     Ответить | Цитировать Сообщить модератору
 Re: задача про ранец  [new]
Wisky
Member

Откуда: Москва
Сообщений: 163
В боевых условия около 350 лотов, 100 покупателей, 7000 заявок (за счет десятка покупателей, которым без разницы, что покупать), ситуация, что лот нужен только одному почти исключена.
18 июн 13, 16:42    [14449190]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить