Is this problem a knapsack problem?

Solve the knapsack problem

• Knapsack Problem (Actually, this is a subset of real http://en.wikipedia.org/wiki/Knapsack_problem.... - there's nothing to optimize!) The knapsack problem is: Given positive integers , and an integer S, find non-negative integers satisfies ... or in (my bad) English... Suppose you have many stuffs which weights , find configurations of those stuffs which weights S. Problem Find all configurations of stuffs, which information is given by input. Input You can make your own format, but you should enable users to input the sum of stuffs(S), weights of stuffs , and names of each stuffs. Stuffs' name may contain [a-zA-Z0-9 _] (alphanumeric + _ + space). You may assume that the input is correct, are positive, and S is non-negative. For example, consider this pseudo-real world situation, where a man orders appetizers worth exactly $15.05: A possible input is: 1505 215 Mixed fruit 275 French fries 335 Side salad 355 Hot wings 420 Mozzarella sticks 580 Sampler plate Output Print all possible configurations (no same configurations, one configuration per one line, each line contains pairs of amount of a stuff and name of the stuff). Stuff with zero amount can be omitted. If there's no configuration possible, simply print X. Example Input and output format (and order) can be vary. This is JS code I made roughly: var s=prompt(),a=s.split('/'),b=[],c,i=1,t=a[0];while(i<a.length){c=a[i].split(/^([^ ]*) /);c.shift();b.push(c);i++;} var d=[],l=b.length,p=0,_=0;for(i=0;i<l;i++)d[i]=0; function as(x,y){for(var i=0,s=0;i<x.length;i++)s+=x[i][0]*y[i];return s} function cs(x,y){for(var i=0,s='';i<x.length;i++)s+=y[i]+' '+x[i][1]+', ';return s} while(p>=0){ p=0; while((q=as(b,d))>=t){ if(q==t){console.log(cs(b,d));_=1} d[p]=0;p++;if(p>=l){p=-1;break;} d[p]++; } if(p==0) d[0]++; } if(!_) console.log('X'); Input 1505/215 Mixed fruit/275 French fries/335 Side salad/355 Hot wings/420 Mozzarella sticks/580 Sampler plate Output 7 Mixed fruit, 0 French fries, 0 Side salad, 0 Hot wings, 0 Mozzarella sticks, 0 Sampler plate, 1 Mixed fruit, 0 French fries, 0 Side salad, 2 Hot wings, 0 Mozzarella sticks, 1 Sampler plate, Input 5/1 A/1 B/1 C Output 5 A, 0 B, 0 C, 4 A, 1 B, 0 C, 3 A, 2 B, 0 C, 2 A, 3 B, 0 C, 1 A, 4 B, 0 C, 0 A, 5 B, 0 C, 4 A, 0 B, 1 C, 3 A, 1 B, 1 C, 2 A, 2 B, 1 C, 1 A, 3 B, 1 C, 0 A, 4 B, 1 C, 3 A, 0 B, 2 C, 2 A, 1 B, 2 C, 1 A, 2 B, 2 C, 0 A, 3 B, 2 C, 2 A, 0 B, 3 C, 1 A, 1 B, 3 C, 0 A, 2 B, 3 C, 1 A, 0 B, 4 C, 0 A, 1 B, 4 C, 0 A, 0 B, 5 C, Input 10/20 A/11 B Output X Input 250/35 Portal 2/21 Minecraft/12 Braid Output 5 Portal 2, 3 Minecraft, 1 Braid, 2 Portal 2, 8 Minecraft, 1 Braid, 2 Portal 2, 4 Minecraft, 8 Braid, 2 Portal 2, 0 Minecraft, 15 Braid, Input 250/33 Portal 2/21 Minecraft/12 Braid Output X Winner Since this is the code golf game, person with shortest code win. If two codes have same length, then a code with highest votes win.

• Answer:

  Python, 185 chars S,C,N=input() R=range(len(C)) F=lambda i,w:sum([[x+[j]for x in F(j,w-C[j])]for j in R[i:]],[])if w>0 else[[]][w<0:] for L in F(0,S):print[(L.count(i),N[i])for i in R];S=0 if S:print'X' run it with input like this: echo "[1505,[215,275,335,355,420,580],['MF','FF','SS','HW','MS','SP']]" | ./knapsack.py which encodes S, a list of costs, and a list of item names corresponding to those costs. It outputs list of item counts and item names: [(7, 'MF'), (0, 'FF'), (0, 'SS'), (0, 'HW'), (0, 'MS'), (0, 'SP')] [(1, 'MF'), (0, 'FF'), (0, 'SS'), (2, 'HW'), (0, 'MS'), (1, 'SP')]