BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
Jrunner1569
Calcite | Level 5

Hello all,

 

I'm working on a variation of the subset-sum problem or knapsack problem. Here's the situation:

 

I have several subsets that I need to choose 1 item from each. All of the selected items need to sum to a target specified. I need all possible combinations that sum to target.

 

Here's a visual:

 

list1 = {0, 26, 44};

list2 = {0, 52, 65, 78};

list3 = {0, 4, 12, 20, 27, 46};

 

target = 116;

 

So one output from the program would be: 44, 52, 20.

It's important to me that the solution retains the order the item lists are in. So seeing 52, 20, 44 as a solution is not preferred.

Also 26, 44, 46 can NOT be a solution, as it uses 2 items from list1. The solution must only use 1 item from each list.

 

Hopefully this makes sense! Thank you so much!

 

Justin

1 ACCEPTED SOLUTION

Accepted Solutions
ballardw
Super User

Data step solution for the given exact problem

data example;
   Array l1 (2 ) _temporary_ (0, 47);
   Array l2 (2 ) _temporary_ (0, 45);
   Array l3 (2 ) _temporary_ (0, 49);
   Array l4 (3 ) _temporary_ (0, 42, 60);
   Array l5 (2 ) _temporary_ (0, 44);
   Array l6 (3 ) _temporary_ (0, 26, 44);
   Array l7 (4 ) _temporary_ (0, 52, 65, 78);
   Array l8 (6 ) _temporary_ (0, 4, 12, 20, 27, 38);
   Array l9 (2 ) _temporary_ (0, 46);
   Array l10(5 ) _temporary_ (0, 18, 33, 40, 42);
   Array l11(3 ) _temporary_ (0, 29, 39);
   Array l12(3 ) _temporary_ (0, 41, 48);
   target=505;
   do a=1 to dim (l1);
   do b=1 to dim (l2);
   do c=1 to dim (l3);
   do d=1 to dim (l4);
   do e=1 to dim (l5);
   do f=1 to dim (l6);
   do g=1 to dim (l7);
   do h=1 to dim (l8);
   do i=1 to dim (l9);
   do j=1 to dim (l10);
   do k=1 to dim (l11);
   do l=1 to dim (l12);
     if sum(l1[a],l2[b],l3[c],l4[d],l5[e],l6[f],l7[g],l8[h],
            l9[i],l10[j],l11[k],l12[l] )=target then do;
         v1 = l1[a] ;
         v2 = l2[b] ;
         v3 = l3[c] ;
         v4 = l4[d] ;
         v5 = l5[e] ;
         v6 = l6[f] ;
         v7 = l7[g] ;
         v8 = l8[h] ;
         v9 = l9[i] ;
         v10= l10[j];
         v11= l11[k];
         v12= l12[l]; 
         output;
     end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   keep target v1-v12;
run;

But I don't see a way to partition your long list into the sub-lists specified without some sort of rules involved.

 

You could build a loop with different values of target if needed.

View solution in original post

9 REPLIES 9
Rick_SAS
SAS Super FREQ

Please post the program that shows what you've tried so far. That will make it easier for us to modify it.

Jrunner1569
Calcite | Level 5

Hey Rick,

 

The only thing I've experimented with so far is a solution you provided on this forum a few years ago to a similar question. Code is below:

 

proc iml;

items = {0, 4, 12, 18, 20, 26, 27, 29, 33, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 52, 60, 65, 78};

target = 505;

 

N = nrow(items);

do k = 1 to N;

a = allcomb(N, k); /* all combs taken k at a time */

m = shape(items[a], 0, k); /* make matrix with k rows */

idx = loc(m[,+] = target); /* rows whose sum = target */

if ncol(idx)>0 then

 

print (m[idx,]);

end;

 

 

The difference is, the items list above is a single subset. I need something more like this with the above target:

 

list1 = {0, 47};

list2 = {0, 45};

list3 = {0, 49};

list4 = {0, 42, 60};

list5 = {0, 44};

list6 = {0, 26, 44};

list7 = {0, 52, 65, 78};

list8 = {0, 4, 12, 20, 27, 38};

list9 = {0, 46};

list10 = {0, 18, 33, 40, 42};

list11 = {0, 29, 39};

list12 = {0, 41, 48};

 

Also, this line: if ncol(idx)>0

would need to be changed because ncol = 12 every time.

ballardw
Super User

Data step solution for the given exact problem

data example;
   Array l1 (2 ) _temporary_ (0, 47);
   Array l2 (2 ) _temporary_ (0, 45);
   Array l3 (2 ) _temporary_ (0, 49);
   Array l4 (3 ) _temporary_ (0, 42, 60);
   Array l5 (2 ) _temporary_ (0, 44);
   Array l6 (3 ) _temporary_ (0, 26, 44);
   Array l7 (4 ) _temporary_ (0, 52, 65, 78);
   Array l8 (6 ) _temporary_ (0, 4, 12, 20, 27, 38);
   Array l9 (2 ) _temporary_ (0, 46);
   Array l10(5 ) _temporary_ (0, 18, 33, 40, 42);
   Array l11(3 ) _temporary_ (0, 29, 39);
   Array l12(3 ) _temporary_ (0, 41, 48);
   target=505;
   do a=1 to dim (l1);
   do b=1 to dim (l2);
   do c=1 to dim (l3);
   do d=1 to dim (l4);
   do e=1 to dim (l5);
   do f=1 to dim (l6);
   do g=1 to dim (l7);
   do h=1 to dim (l8);
   do i=1 to dim (l9);
   do j=1 to dim (l10);
   do k=1 to dim (l11);
   do l=1 to dim (l12);
     if sum(l1[a],l2[b],l3[c],l4[d],l5[e],l6[f],l7[g],l8[h],
            l9[i],l10[j],l11[k],l12[l] )=target then do;
         v1 = l1[a] ;
         v2 = l2[b] ;
         v3 = l3[c] ;
         v4 = l4[d] ;
         v5 = l5[e] ;
         v6 = l6[f] ;
         v7 = l7[g] ;
         v8 = l8[h] ;
         v9 = l9[i] ;
         v10= l10[j];
         v11= l11[k];
         v12= l12[l]; 
         output;
     end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   end;
   keep target v1-v12;
run;

But I don't see a way to partition your long list into the sub-lists specified without some sort of rules involved.

 

You could build a loop with different values of target if needed.

IanWakeling
Barite | Level 11

It's possible to get there without using loops by making use of the EXPANDGRID function, and it can be generalized to any number of lists by constructing the required EXPANDGRID call in a string and then using CALL EXECUTE.   Here is some code illustrating the smaller problem that you posted.

 

proc iml;

start knap;
  /* make matrix of all the lists with missing value padding */
  lists = {0 26 44  .  .  .,
           0 52 65 78  .  .,
           0  4 12 20 27 46};
  target = 116;

  /* create binary matrix indicating where the list values are */
  values = lists>.;

  longlist = lists[loc(values)];  /* make one long list */
  n = values[ , +];
  /* work out where each individual list starts and end in longlist */
  m = (1 + cusum(n) - n) || cusum(n);

  s = rowcat( t( cats( char(m[,1]), ':', char(m[,2]), ',' )));
  s = cats( 'e = expandgrid(', s, ');' );
  print s; /* show the command s that is about to be executed */
  call execute(s);

  /* all possible combinations of values, one from each list */
  c = shape( longlist[e], nrow(e), nrow(lists));

  /* now use Rick's trick */
  idx = loc(c[,+] = target);

  if ncol(idx)>0
    then print 'Target found :', (c[idx,]);
    else print 'Target not found';

finish;

run knap;

quit;
Jrunner1569
Calcite | Level 5

I appreciate all of the quick responses! I don't have the OR product package for some of these solutions so I went with the data step solution provided by bollardw. Thanks everyone! I applied a quick macro wrapper with a target list and appended them together. Did exactly what I needed! 🙂

Ksharp
Super User

It is more like a OR problem than IML .

Better post it at OR Forum and calling @RobPratt 

RobPratt
SAS Super FREQ
proc optmodel;
   num numLists = 3;
   set LIST {1..numLists};
   LIST[1] = {0, 26, 44};
   LIST[2] = {0, 52, 65, 78};
   LIST[3] = {0, 4, 12, 20, 27, 46};
   num target = 116;

   /* X[i,j] = 1 if list i, item j is chosen; 0 otherwise */
   var X {i in 1..numLists, j in LIST[i]} binary;

   con OneItemPerList {i in 1..numLists}:
      sum {j in LIST[i]} X[i,j] = 1;

   con SumToTarget:
      sum {i in 1..numLists, j in LIST[i]} j * X[i,j] = target;

   solve with clp / findallsolns;
   set SUPPORT {s in 1.._NSOL_} = {i in 1..numLists, j in LIST[i]: X[i,j].sol[s] > 0.5};
   put SUPPORT[*];
quit;

{<1,44>,<2,52>,<3,20>} {<1,26>,<2,78>,<3,12>}

Ksharp
Super User
data list1;
input list1  ;
cards;
0 
26
44
;

data list2;
input list2  ;
cards;
0 
52
65
78
;

data list3;
input list3  ;
cards;
0 
4
12
20
27
46
;

 proc sql;
  select *
   from (select list1 from list1),(select list2 from list2),(select list3 from list3)
    where sum(list1,list2,list3)=116;
 quit;
Rick_SAS
SAS Super FREQ

Great answer from @Ksharp . You can do the same thing in IML by using the ExpandGrid function:

 

proc iml;
L1 = {0 26 44};
L2 = {0 52 65 78};
L3 = {0  4 12 20 27 46};
target = 116;
G = ExpandGrid(L1, L2, L3);
idx = loc( G[,+]=target );
if ncol(idx)>0 then 
   soln = G[idx,];
else soln=.;  /* no soln */
print soln;

sas-innovate-2024.png

Don't miss out on SAS Innovate - Register now for the FREE Livestream!

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

 

Register now!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

From The DO Loop
Want more? Visit our blog for more articles like these.
Discussion stats
  • 9 replies
  • 1148 views
  • 5 likes
  • 6 in conversation