473,883 Members | 1,682 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Help me rid my curse... please.

I have been losing sleep over this puzzle, and I'm convinced my train
of thought is heading in the wrong direction. It is difficult to
explain my circumstances, so I will present an identical make-believe
challenge in order to avoid confusing the issue further.

Suppose I was hosting a dinner and I wanted to invite exactly 12 guests
from my neighborhood. I'm really picky about that... I have 12 chairs
besides my own, and I want them all filled or there ain't gonna be no
dinner.

I have created a table of all the families in my neighborhood that I
can tolerate for an hour, and a count of all the members in each of the
families. I added an identity column and prioritized my potential
guests by the size of each family in descending order, like so:

Identity FamilyName SeatsNeeded
1 McClusky 8
2 Olson 7
3 Adams 6
4 Wilson 3
5 Sayjak 2

What is the easiest way to identify the first or only group of guests
that required EXACTLY 12 seats? The only solution, by the way, is to
invite the McClusky's, the Wilson's and the Sayjak's (7+3+2=12).

The procedure I am currently using starts with the table #ungrouped
(similar to the example above), and inserts the first record from
#ungrouped into an empty table, #grouped (set up just like #ungrouped,
except records from "SeatsNeede d" become "SeatsTaken "). While the sum
of all SeatsTaken in #grouped is less than 12, I continue to add to it
unique records from #ungrouped where SeatsNeeded
<=(12-SUM(#grouped.Se atsTaken)). As soon as #grouped contains a total
of 12 under the SeatsTaken column, those records are tagged with a
GroupID in their source tables and removed from the temporary tables.
The process is repeated until the procedure can't find any more groups
of 12 (if a situation exists similar to my example table, I have to
identify the last group manually). The remaining records get grouped
when additional records become available.

I apologize if my SQuengLish is confusing or in any way insulting. I
guess the bottom line is that I have a solution that only works when
the first records is part of the result set, and the procedure has many
more records to sort through. It would be nice if I could find as many
groups of 12 as possible, as efficiently as possible, with as few
left-overs as possible.

Any ideas? Clues?

Silvio

Jul 23 '05 #1
28 3312
Silvio Again...

I made a mistake regarding my example record set. If I want to iscolate
the records where the sum of all values in SeatsNeaded was 12, from
this table:

Identity FamilyName SeatsNeeded
1 McClusky 8
2 Olson 7
3 Adams 6
4 Wilson 3
5 Sayjak 2

.... the correct record set would include the OLSON's, the Wilson's and
the Sayjak's (7+3+2=12)... not the McClusky's.

Jul 23 '05 #2
On 20 Jan 2005 07:56:22 -0800, stu_gots wrote:

(snip)
Suppose I was hosting a dinner and I wanted to invite exactly 12 guests
from my neighborhood. I'm really picky about that... I have 12 chairs
besides my own, and I want them all filled or there ain't gonna be no
dinner.

(snip)

Hi Silvio,

I don't have a ready-made solution for this particular problem. I do have
a solution to a related problem, that might or might not help. I'll get to
that later on in this message. First, some thoughts about your problem.

An interesting starting question is whether there is a mathematical
solution for this problem - I'm not a mathematician, but maybe someone
else reading this is?
Anyway, if there is no mathematical solution, or if it is too complicated
to use in SQL Server, your only other option is to use trial and error. In
a third generation programming language, I'd be tempted to make a
recursive procedure:
* add largest family that still fits room to the "to be invited" set
* if all seats filled: report success & return
* if empty seats left:
* call self
* if succes: report succes & return
* if failure: retry from start with next available family
* if all families have been tried: report failure & return
You COULD try to create such a procedure in SQL Server, but recursion is
not exactly a particular strength of SQL Server. It would also perform
terrible (from the rest of your message, I understand that your real
problem involves lots more families and not one but many dinner parties).

I'll mull your problem over for a while. If I come up with something
creative, I'll let you know.
Meanwhile, allow me to present you with the code I once wrote to solve a
related problem. To stay with your analogy: you have to invite ALL guests
from your neighbourhood to dinner; you want to get it over as quickly as
possible, so if you can serve them all with three dinner aprties, there
definitely won't be four. I bet you see both the similarities and the
differences; I'll leave it to you to decide if this code will help you or
not.

The code I'll post uses a different analogy: examinations. There are
different subjects (families); for each subject, the number of students
that enrolled for the exam (family members) is known. The examination room
has a capacity of 100 seats. All students taking an examination for a
subject will be invited on the same day; examination sessions for multiple
subjects might be combined as long as the room doesn't overflow. The aim
of my code is to combine as much subjects as possible, making sure the
least possible amount of days is used to get all examinations done. I
don't think my code will always find the best possible combination, but I
do believe that it gets pretty close, and it's a lot faster than using
cursors (as most peeple would do in this case).

Some extra complications in my example that are not present in your
analogy are:
* If more than 100 students enroll for the same subject (and only in that
case!), the examinations for that subject will be split: as many sessions
for exactly 100 students as needed, plus one session for the remaining
students. This last session might be combined with sessions for other
subjects.
* The examinations are not help once, but each quarter; the number of
students enrolling for a subject might change from quarter to quarter.

Here's the code I used to solve this. I originally wrote this script for
Joe Celko, so I used the ANSI-standard UPDATE syntax; converting it to
proprietary UPDATE FROM syntax would probably speed it up.

-- Create the tables
CREATE TABLE Entries (Quarter int NOT NULL
,SubjCode char(3) NOT NULL
,NumberOfCandid ates int NOT NULL
,PRIMARY KEY (Quarter, SubjCode)
-- ,FOREIGN KEY (SubjCode) REFERENCES Subjects
,CHECK (Quarter IN (1, 2, 3, 4))
,CHECK (NumberOfCandid ates > 0)
)
CREATE TABLE Sessions (Quarter int NOT NULL
,SessionNo int NOT NULL
,SpaceLeft int NOT NULL -- could be derived, but
that would hurt performance
,PRIMARY KEY (Quarter, SessionNo)
,CHECK (Quarter IN (1, 2, 3, 4))
)
CREATE TABLE SplitEntries (Quarter int NOT NULL
,SubjCode char(3) NOT NULL
,SplitNo int NOT NULL
,NumberOfCandid ates int NOT NULL
,SessionNo int DEFAULT NULL
,PRIMARY KEY (Quarter, SubjCode, SplitNo)
,FOREIGN KEY (Quarter, SubjCode) REFERENCES
Entries
,FOREIGN KEY (Quarter, SessionNo) REFERENCES
Sessions
-- ,CHECK (Quarter IN (1, 2, 3, 4))
-- ,CHECK (NumberOfCandid ates > 0 AND
NumberOfCandida tes <= 100)
)
go

-- Insert some sample data
INSERT Entries (Quarter, SubjCode, NumberOfCandida tes)
SELECT 1, 'A01', 117
UNION ALL
SELECT 1, 'A02', 30
UNION ALL
SELECT 1, 'A03', 263
UNION ALL
SELECT 1, 'A04', 15
UNION ALL
SELECT 1, 'B01', 57
UNION ALL
SELECT 1, 'B02', 32
UNION ALL
SELECT 1, 'B03', 14
UNION ALL
SELECT 2, 'A01', 198
UNION ALL
SELECT 2, 'A02', 54
UNION ALL
SELECT 2, 'A03', 202
UNION ALL
SELECT 2, 'A04', 19
UNION ALL
SELECT 2, 'B01', 42
UNION ALL
SELECT 2, 'B02', 40
UNION ALL
SELECT 2, 'B03', 18
UNION ALL
SELECT 2, 'B04', 16
go

-- Find subjects with over 100 entries, split them in units of max 100.
-- Declare max candidates per session as constant, to make maintenance
easier
DECLARE @MaxCandidatesP erSession int
SET @MaxCandidatesP erSession = 100

-- Make split entries for each full 100 in the original entries
-- A numbers table is needed for this step,
-- see http://www.aspfaq.com/show.asp?id=2516
INSERT INTO SplitEntries (Quarter, SubjCode, SplitNo, NumberOfCandida tes)
SELECT Entries.Quarter ,
Entries.SubjCod e,
numbers.n / @MaxCandidatesP erSession,
@MaxCandidatesP erSession
FROM Entries
INNER JOIN numbers
ON numbers.n <= Entries.NumberO fCandidates
AND numbers.n % @MaxCandidatesP erSession = 0
UNION ALL
-- don't forget the remaining candidates after alloting the full 100's.
SELECT Entries.Quarter ,
Entries.SubjCod e,
1 + Entries.NumberO fCandidates / @MaxCandidatesP erSession,
Entries.NumberO fCandidates % @MaxCandidatesP erSession
FROM Entries
WHERE Entries.NumberO fCandidates % @MaxCandidatesP erSession <> 0

-- Here comes the code to combine the (split) entries into as little
-- examination sessions as possible.
-- Declare max candidates per session as constant, to make maintenance
easier
DECLARE @MaxCandidatesP erSession int
SET @MaxCandidatesP erSession = 100

-- Helper variables to control WHILE loops
DECLARE @AllDone char(1)
SET @AllDone = 'N'
DECLARE @SessionsFull char(1)

-- For each quarter, compute the minimal number of sessions needed and
insert rows for those sessions.
-- Note: minimal number of sessions needed = total applications / max per
session, rounded up.
-- A numbers table is needed for this step,
-- see http://www.aspfaq.com/show.asp?id=2516
INSERT INTO Sessions (Quarter, SessionNo, SpaceLeft)
SELECT Quarter,
(SELECT COALESCE(MAX(s. SessionNo), 0)
FROM Sessions AS s
WHERE s.Quarter = NeedByQuarter.Q uarter) + n,
@MaxCandidatesP erSession
FROM (SELECT Quarter,
(SUM(NumberOfCa ndidates) + @MaxCandidatesP erSession -
1) / @MaxCandidatesP erSession AS MinNeeded
FROM SplitEntries
GROUP BY Quarter) AS NeedByQuarter
CROSS JOIN numbers
WHERE n BETWEEN 1 AND NeedByQuarter.M inNeeded
-- Keep adding and filling sessions until all split entries are assigned a
session
WHILE @AllDone = 'N'
BEGIN
SET @SessionsFull = 'N'

-- Keed adding split entries to sessions until they are all as full as
possible
WHILE @SessionsFull = 'N'
BEGIN
-- Add another split entry to each session that still has room for
another split entry.
-- Note that this is not a best fit algorithm, but rather a compromise
-- to keep the query simple (cough) and limit execution time.
-- Each session gets a ranking based on descending SpaceLeft (within
quarter), with SessionNo as tiebreaker.
-- Each split entry gets a ranking, based on descending
NumberOfCandida tes (within quarter),
-- with SubjectCode and SplitNo as tiebreakers.
-- Split entries that won't fit any available session are omitted -
they'll wait for the next round of sessions.
-- The tables are joined on rank and if the NumberOfCandida tes doesn't
exceed the space left, it is added.
-- The subquery is repeated twice, to satisfy ANSI standard syntax.
-- Execution time on MS SQL Server decreases if proprietary T-SQL
update syntax is used.
UPDATE SplitEntries
SET SessionNo = (SELECT s.SessionNo
FROM Sessions AS s
WHERE s.Quarter = SplitEntries.Qu arter
AND s.SpaceLeft >=
SplitEntries.Nu mberOfCandidate s
AND (SELECT COUNT(*)
FROM Sessions AS s2
WHERE s2.Quarter =
SplitEntries.Qu arter
AND (s2.SpaceLeft > s.SpaceLeft
OR (s2.SpaceLeft = s.SpaceLeft
AND s2.SessionNo <=
s.SessionNo)))
= (SELECT COUNT(*)
FROM SplitEntries AS se2
WHERE se2.Quarter =
SplitEntries.Qu arter
AND se2.SessionNo IS
NULL
AND se2.NumberOfCan didates <=
(SELECT MAX(SpaceLeft)

FROM Sessions AS s3

WHERE s3.Quarter = SplitEntries.Qu arter)
AND (se2.NumberOfCa ndidates >
SplitEntries.Nu mberOfCandidate s
OR (se2.NumberOfCa ndidates =
SplitEntries.Nu mberOfCandidate s
AND se2.SubjCode <
SplitEntries.Su bjCode)
OR (se2.NumberOfCa ndidates =
SplitEntries.Nu mberOfCandidate s
AND se2.SubjCode =
SplitEntries.Su bjCode
AND se2.SplitNo <=
SplitEntries.Sp litNo))))
WHERE SessionNo IS NULL
AND NumberOfCandida tes <= (SELECT MAX(SpaceLeft)
FROM Sessions AS b3
WHERE b3.Quarter =
SplitEntries.Qu arter)
AND EXISTS (SELECT s.SessionNo
FROM Sessions AS s
WHERE s.Quarter = SplitEntries.Qu arter
AND s.SpaceLeft >= SplitEntries.Nu mberOfCandidate s
AND (SELECT COUNT(*)
FROM Sessions AS s2
WHERE s2.Quarter = SplitEntries.Qu arter
AND (s2.SpaceLeft > s.SpaceLeft
OR (s2.SpaceLeft = s.SpaceLeft
AND s2.SessionNo <= s.SessionNo)))
= (SELECT COUNT(*)
FROM SplitEntries AS se2
WHERE se2.Quarter = SplitEntries.Qu arter
AND se2.SessionNo IS NULL
AND se2.NumberOfCan didates <= (SELECT
MAX(SpaceLeft)
FROM
Sessions AS s3
WHERE
s3.Quarter = SplitEntries.Qu arter)
AND (se2.NumberOfCa ndidates >
SplitEntries.Nu mberOfCandidate s
OR (se2.NumberOfCa ndidates =
SplitEntries.Nu mberOfCandidate s
AND se2.SubjCode <
SplitEntries.Su bjCode)
OR (se2.NumberOfCa ndidates =
SplitEntries.Nu mberOfCandidate s
AND se2.SubjCode =
SplitEntries.Su bjCode
AND se2.SplitNo <=
SplitEntries.Sp litNo))))

IF @@ROWCOUNT = 0
BEGIN
-- If no updates were done, all sessions are as full as possible and
inner loop stops
SET @SessionsFull = 'Y'
END
ELSE
BEGIN
-- One or more split entries were assigned to a session -
recalculate remaining room in all sessions
UPDATE Sessions
SET SpaceLeft = @MaxCandidatesP erSession
- (SELECT SUM(NumberOfCan didates)
FROM SplitEntries
WHERE SplitEntries.Qu arter = Sessions.Quarte r
AND SplitEntries.Se ssionNo =
Sessions.Sessio nNo)
END
END -- End inner loop (adding split entries to sessions)

-- All sessions are filled as far as possible, but maybe some split
entries are still not allotted to any session.
-- For each quarter, compute and insert the minimal number of extra
sessions needed.
-- (Note - this is basicallly a repeat of the query before the outermost
WHILE loop,
-- with an extra WHERE to skip split entries already assigned to
a session)
INSERT INTO Sessions (Quarter, SessionNo, SpaceLeft)
SELECT Quarter,
(SELECT COALESCE(MAX(s. SessionNo), 0)
FROM Sessions AS s
WHERE s.Quarter = NeedByQuarter.Q uarter) + n,
@MaxCandidatesP erSession
FROM (SELECT Quarter,
(SUM(NumberOfCa ndidates) + @MaxCandidatesP erSession
- 1) / @MaxCandidatesP erSession AS MinNeeded
FROM SplitEntries
WHERE SessionNo IS NULL
GROUP BY Quarter) AS NeedByQuarter
CROSS JOIN numbers
WHERE n BETWEEN 1 AND NeedByQuarter.M inNeeded

IF @@ROWCOUNT = 0
BEGIN
-- No new sessions inserted can only mean that there are no more split
entries with SessionNo still NULL
SET @AllDone = 'Y'
END
END -- End outer loop (adding sessions until all split entries are
alotted)

-- All done!

Sorry for the line wrapping. My SQL code was obviously not formatted with
the 80-character usenet limitation in my mind <g>

Best, Hugo
--

(Remove _NO_ and _SPAM_ to get my e-mail address)
Jul 23 '05 #3
Thanks for the ideas. I'm not sure yet what it was, but soon after I
read your post I came up with a solution. I think I've completely
solved my root problem, and I kind of feeel silly for not seeing it in
the first place... I guess I never found any examples.

Anyway, this seems to be the fastest and easiest way to (in my case) to
identify a group of "orders" where the total number of "sets" = 12.
More on this later, here's what I got so far...

--Again, instead of inviting families to fill exactly 12 seats,
--I'm looking for the fewest OrderIDs
--where the number of Sets they contain totals exactly 12.
--This returns a value of 2,3,7

CREATE TABLE #Example
(
OrderID int,
SetCount int NULL
)

INSERT #Example VALUES (1,8)
INSERT #Example VALUES (2,7)
INSERT #Example VALUES (3,6)
INSERT #Example VALUES (4,3)
INSERT #Example VALUES (5,2)
INSERT #Example VALUES (6,DEFAULT)

SELECT TOP 1 a.SetCount AS SetA,
b.SetCount AS SetB,
c.SetCount AS SetC
FROM #Example a
INNER JOIN #Example b ON a.OrderID <> b.OrderID
INNER JOIN #Example c ON a.OrderID <> c.OrderID
AND c.OrderID <> b.OrderID
GROUP BY a.SetCount, b.SetCount, c.SetCount
HAVING (SUM(a.SetCount + b.SetCount + c.SetCount) = 12)

Jul 23 '05 #4
"stu_gots" <sl*******@yaho o.com> wrote in message
news:11******** *************@c 13g2000cwb.goog legroups.com...
I have created a table of all the families in my neighborhood that I
can tolerate for an hour, and a count of all the members in each of the
families. I added an identity column and prioritized my potential
guests by the size of each family in descending order, like so:

Identity FamilyName SeatsNeeded
1 McClusky 8
2 Olson 7
3 Adams 6
4 Wilson 3
5 Sayjak 2

What is the easiest way to identify the first or only group of guests
that required EXACTLY 12 seats? The only solution, by the way, is to
invite the McClusky's, the Wilson's and the Sayjak's (7+3+2=12).


Ok, I have a solution. It is not going to have fabulous performance but it
seems to work.
The basic procedure that I use is:

Create a List (length = 1) of Families
Loop until length = count(Items)
Find Member Size of Each List
Delete all Lists where Size > desiredsize
If Size = desiredsize add list to Solutions
If you want to shorten runtime and find only smallest solutions end
here.
Build new lists from all remaining lists by adding each family not in the
list to the list.
End

Expanding the list back into the family names is left as an excercise for
the reader.

Regards,
Jim
-- BEGIN SQL
--CREATE SAMPLE DATA
create table #Dining (Fam integer, famname varchar(10), members integer)
insert into #Dining VALUES (1,'McClusky',8 )
insert into #Dining VALUES (2,'Olson',7)
insert into #Dining Values (3,'Adams',6)
insert into #Dining Values (4,'Wilson',3)
insert into #Dining Values (5,'Sayjak',2)
insert into #Dining Values (6,'Test',4)

--CREATE TEMP TABLES FOR PROCESS
create table #sol(fams varchar(200), Total integer, maxfam integer, length
integer)
create table #solution(fams varchar(200), Total integer)

declare @length integer
declare @curmax integer -- Number of Items in table
declare @desiredsize integer

set @desiredsize = 13 -- Size to Find

select @curmax = Count(*) from #Dining
set @length = 1
insert into #sol(fams, maxfam, length) Select Fam, Fam, @length from
#Dining -- Singles

while @length < @curmax
BEGIN
set @length = @length + 1
insert into #sol(fams, maxfam, length ) Select a.Fams + ',' + CAST(b.Fam
as varchar(2)), b.fam, @length
from #sol a, #dining b
where a.maxfam < b.fam
delete #sol where #sol.length < @length
update #sol Set Total = t.mem from (Select Fams, sum(members) mem from
#Dining b, #sol a where ','+a.Fams+',' like '%,'+CAST(b.Fam as
varchar(2))+',% '
Group by Fams) t inner join #sol a on t.Fams = a.Fams

insert into #solution(fams, Total) SELECT #sol.fams, #sol.Total FROM #sol
where Total = @desiredsize

delete #sol where Total > @desiredsize
END

select * from #solution

--CLEAN UP
drop table #Dining
drop table #sol
drop table #solution
--END SQL
Jul 23 '05 #5
To elaborate, I am not interested cutting seconds or preserving system
resources. I'm working in pre-press during a swing shift, assembling
about 200 orders per evening containing a total of about 800 sets. This
is a print production solution... only 12 sets can pass through the
press at once in a variety of different circumstances too difficult to
explain. Orders, by the way, can not be split up to print in different
groups because of consistancy issues, and are consequently not sold in
groups of more than 12.

This will be a long series of loops that applies the grouping procedure
to a bout 20 or more different subgroups of orders. The object will be
to have as few ungrouped orders as possible when the procedure is out
of places to turn. Perhaps there is a better procedure than the cross
join I posted a bit ago (the full context of which would actually
return 12 values... '2', '3', '7', and nine NULLs... I just gave you
the abridged version). The reason I'm so thrilled my the cross join is
that it will do the job a lot better than the current method of
grouping orders (with two hands and a pot of coffee), and it is simple
enough for the beginner... someone will have to take over for me
eventually. I have a long way to go before I can automate the process,
but I'm pretty sure the most difficult brain-teasers are behind me.
What do you think... errors in my logic?

-badabing!

Jul 23 '05 #6
The following code will return all the permutations of 3 families to
get the result. It returns families #2, #4, #5. I couldn't figure out
how to narrow the permutations down to only combinations though.
select A,B,C
from
(
select a.orderid as A, b.orderid as B, c.orderid as C,
isnull(a.setcou nt,0) as AA, isnull(b.setcou nt,0) as BB,
isnull(c.setcou nt,0) as CC
from #Example A, #Example B, #Example C
) Derived
where
A<>B and A<>C and B<>C and
(AA+BB+CC) =12

Jul 23 '05 #7
Just thought it thru. Added top clause and order by clause. It now
returns one row #2, #4, #5. (Bonus style points for me :) Note this
only checks for combinations of 3 families. You'll need to modify for
combos of 4 etc.

select top 1 A,B,C
from
(
select a.orderid as A, b.orderid as B, c.orderid as C,
isnull(a.setcou nt,0) as AA, isnull(b.setcou nt,0) as BB,
isnull(c.setcou nt,0) as CC
from #Example A, #Example B, #Example C
) Derived
where
A<>B and A<>C and B<>C and
(AA+BB+CC) =12
order by A,B,C

Jul 23 '05 #8
Exactly what I was thinking. I suppose I could make use of up to 12
output fields (A, B, C, ..., K, L). Most of them would never contain
more than Null anyway, and I'd have them in the rare instance when my
procedure came down to a final group of 12 Orders, all with one set.

Jul 23 '05 #9
"stu_gots" <sl*******@yaho o.com> wrote in message
news:11******** *************@c 13g2000cwb.goog legroups.com...
This will be a long series of loops that applies the grouping procedure
to a bout 20 or more different subgroups of orders. The object will be
to have as few ungrouped orders as possible when the procedure is out
of places to turn. Perhaps there is a better procedure than the cross
join I posted a bit ago (the full context of which would actually
return 12 values... '2', '3', '7', and nine NULLs... I just gave you
the abridged version). The reason I'm so thrilled my the cross join is
that it will do the job a lot better than the current method of
grouping orders (with two hands and a pot of coffee), and it is simple
enough for the beginner... someone will have to take over for me
eventually. I have a long way to go before I can automate the process,
but I'm pretty sure the most difficult brain-teasers are behind me.
What do you think... errors in my logic?

-badabing!

The Join that you have seems that it will work, however it looks difficult
to maintain to me, especially if the batch size changes. Is there some
reason you are subgrouping your orders? BTW this is a variant of a problem
called the Bin-Packing Problem and this problem is considered mathematically
hard (Technically, NP-Complete, for all of you geeks out there). The upshot
of which is that finding the 'best' solution isn't possible for the general
case in a reasonable amount of time. (While I know you said you aren't
concerned about time, reasonable in this case goes into hundreds of years
for not terrible large sets of data). For example: With the minimal data
set (5 samples) in the sample there are 27 different possible batches. With
10 there are 1014. With 200 there are 1.6x10^60.

Having Said that, I have made a couple revisions to accomodate batch
assignment. It will assign all jobs possible to batches, each batch will
have SetQty of 12. The Remainder of Jobs will not be batchable for Qty 12.
The current ordering creates each batch with the smallest number of jobs and
I suspect this to be reasonable at batching the most possible jobs, although
this is not guaranteed. The only caveat in the current routine is that any
set with qty 12 gets set to Batch #0 to indicate it must be run separately.
Ideally each of these should be given individual batch numbers and probably
the batches should be prioritized in some manner.

Let me know how it goes.

Jim

--BEGIN SQL
--CREATE SAMPLE DATA
create table #Jobs (JobNum integer, JobName varchar(10), Qty integer)
insert into #Jobs VALUES (1,'McClusky',8 )
insert into #Jobs VALUES (2,'Olson',7)
insert into #Jobs Values (3,'Adams',6)
insert into #Jobs Values (4,'Wilson',3)
insert into #Jobs Values (5,'Sayjak',2)
insert into #Jobs Values (6,'Test',4)
insert into #Jobs VALUES (7,'MAX',12)
--CREATE TEMP TABLES FOR PROCESSING
create table #sol(JobNums varchar(200), Total integer, maxJobNum integer,
length integer)
create table #solution(JobNu ms varchar(200), Total integer)
create table #batches(batchn um integer, setnum integer, qty integer)

--DECLARE VARIABLES
declare @length integer
declare @curmax integer
declare @desiredsize integer
declare @found integer
declare @done integer
declare @batchnum integer

set @desiredsize = 12 -- BATCH SIZE SHOULD BE PASSED INTO SP
set @done = 0
set @batchnum = 0

-- SINCE EACH SET MUST BE > 0 THERE CAN BE NO MORE THAN 12 SETS IN A VALID
SOLUTION
set @curmax = @desiredsize

-- SET ALL SINGLES to Batch #0
insert into #batches SELECT @batchnum, JobNum, Qty From #Jobs where Qty =
@desiredsize

While (@done = 0)
BEGIN
delete from #sol
set @length = 1
--START WITH SINGLE SET BATCHES
insert into #sol(JobNums, maxJobNum, length)
Select JobNum, JobNum, @length
from #Jobs left join #batches on #Jobs.JobNum = #batches.SetNum
where SetNum is Null -- Singles
set @found = 0
while (@length < @curmax) and (@found = 0)
BEGIN
set @length = @length + 1
--ADD A SET TO EACH BATCH
insert into #sol(JobNums, maxJobNum, length ) Select a.JobNums + ',' +
CAST(b.JobNum as varchar(2)), b.JobNum, @length
from #sol a, (#Jobs b left join #batches c on b.JobNum =
c.SetNum)
where a.maxJobNum < b.JobNum and c.SetNum is Null
--DELETE SMALLER BATCHES
delete #sol where #sol.length < @length
--CALC BATCH SIZE
update #sol Set Total = t.mem from (Select JobNums, sum(Qty) mem from
#Jobs b, #sol a where ','+a.JobNums+' ,' like '%,'+CAST(b.Job Num as
varchar(2))+',% '
Group by JobNums) t inner join #sol a on t.JobNums = a.JobNums

--SET SOLUTIONS IF BATCH SIZE = DESIRED SIZE
insert into #solution(JobNu ms,Total) SELECT #sol.JobNums, #sol.Total
FROM #sol where Total = @desiredsize
IF @@ROWCOUNT > 0
BEGIN
--IF FOUND START OVER
set @found = 1
END
--GET RID OF ALL TOO LARGE BATCHES
delete #sol where Total >= @desiredsize
END
IF @found=0 --WE SIZED OUT SO WE ARE DONE
BEGIN
set @done = 1
END
--ASSIGN FOUND SOLUTIONS TO A BATCH
set @batchnum = @batchnum+1
insert into #batches select @batchnum, a.JobNum, a.Qty from #Jobs a inner
join #solution b on ','+b.JobNums+' ,' like '%,'+CAST(a.Job Num as
varchar(2))+',% '
delete from #solution
END

--SHOW FOUND BATCHES
select * from #batches
--SHOW REMAINDER
select a.* from #Jobs a left join #batches b on a.JobNum = b.SetNum where
b.SetNum is null

drop table #Jobs
drop table #sol
drop table #solution
drop table #batches

Jul 23 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
1610
by: **ham | last post by:
"Visual Studio .NET has detected that the specified Web server is not running ASP.NET version 1.1. You will be unable to run ASP.NET Web applications or services." This is the message I get each time that I want to create an ASP.NET application. The help recommends to register ASP.NET by using the command line and "aspnet_regiis /i" . I do this and there is no error during registration. But again when I try to create an ASP.NET...
15
5189
by: NickName | last post by:
Task: Create 100 or so stored procedure scripts similar to the convention of Generating Script from EM automatically. I thought of essentially two things of a) using sp_helptext to get the content of a sp; and b) using bcp to write such content to a (dynamic) file. What bugs me is really the curse of dynamic sql. process inside a cursor: ------------------------ exec master..xp_cmdshell 'bcp "exec sp_helptext '+@spName+'" queryout
7
3637
by: x muzuo | last post by:
Hi guys, I have got a prob of javascript form validation which just doesnt work with my ASP code. Can any one help me out please. Here is the code: {////<<head> <title>IIBO Submit Page</title> </head> <style type="text/css">
5
3008
by: Craig Keightley | last post by:
Please help, i have attached my page which worksin IE but i cannnot get the drop down menu to fucntion in firefox. Any one have any ideas why? Many Thanks Craig <<<<<<<<<<<<<<CODE>>>>>>>>>>>>>>>> <html>
12
1935
by: aj902 | last post by:
Hello , I am trying to create a program where all detail, http://www.albany.edu/~csi333/projects.htm
23
3303
by: Jason | last post by:
Hi, I was wondering if any could point me to an example or give me ideas on how to dynamically create a form based on a database table? So, I would have a table designed to tell my application to create certain textboxes, labels, and combo boxes? Any ideas would be appreciated. Thanks
2
1871
by: Greg Corradini | last post by:
Hello All, A few weeks ago, I wrote two scripts using mx.ODBC on an Access DB. Among other things, both scripts create new tables, perform a query and then populate the tables with data in a dictionary that I've uploaded from elsewhere. These scripts have run hundreds of times in the last few weeks with no problems. But recently they continue to bail on the mycursor.execute('An SQL Statement') after the table has been created. I get the...
19
3328
by: Ganesh J. Acharya | last post by:
Hi there, I want to redesign my website and make that look professional. I made this about 6 years ago with very little knowledge of internet. Today I am getting about 4000 visitors a day for the same. What are the things I need to keep in my mind when doing this process.
22
4047
by: Chuck Connors | last post by:
Hey guys. I'm working on a little program to help my wife catalog her/ our coupons. I found a good resource but need help formatting the text data so that I can import it into a mysql database. Here's the data format: 409220000003 Life Fitness Products $1 (12-13-08) (CVS) 546500181141 Oust Air Sanitizer, any B1G1F up to $3.49 (1-17-09) .35 each 518000159258 Pillsbury Crescent Dinner Rolls, any .25 (2-14-09) 518000550406 Pillsbury...
0
9933
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11114
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10835
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10407
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9563
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5787
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5982
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4605
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4205
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.