Variation of Knapsack Problem

[Jrunner1569]

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

[Rick_SAS]

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

[Jrunner1569]

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 · Accepted solution]

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]

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]

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]

It is more like a OR problem than IML .

Better post it at OR Forum and calling @RobPratt 

[RobPratt]

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]

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]

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;