Solve the knapsack problem

Knapsack Problem

(Actually, this is a subset of real 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;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]*y[i];return s} function cs(x,y){for(var i=0,s='';i<x.length;i++)s+=y[i]+' '+x[i]+', ';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++; } 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. • How does it make sense to count \n but not \r? That's just favoring certain platforms, and/or tools that don't care which you use. – Matthew Read Sep 28 '11 at 20:15 • @Matthew It's for Windows - since it uses \r\n while Linux uses \n, the amount of code in Windows is increased by number of lines. – JiminP Sep 28 '11 at 22:04 • Wait, does Mac use \r? – JiminP Sep 28 '11 at 22:05 • OK, -1 then. There are so many things wrong with that (besides the bias that is in no way related to the problem). To start: I use Linux line endings in my files on Windows, and the code samples here don't tell you what's what. – Matthew Read Sep 28 '11 at 22:07 • This has been beaten to death already, the consensus is that line endings are equal on whatever platform, no need to discuss/even mention it over and over again. meta.codegolf.stackexchange.com/questions/167/… – J B Sep 28 '11 at 22:30 4 Answers 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')]  Mathematica, 59 chars Tally/@IntegerPartitions[#1,All,#2/._[x_,_]->x]/.#2/.{}->X&  Invoke with %[1505, {215 -> "MF", 275 -> "FF", 335 -> "SS", 355 -> "HW", 420 -> "MS", 580 -> "SP"}]  Ruby, 136 characters a,*b=*$<
c=->s,u,e{f,*r=e;f ?(0..s/h=f.to_i).map{|n|c[s-n*h,u+[n.to_s+f[/ .*/]],r]}:s>0?[]:u*?,}
r=c[a.to_i,[],b].flatten
puts r?r:?X


Input must be given on STDIN, one line for the total amount and then one line per item (weight, followed by space, followed by name).

Example input:

250
35 Portal 2
21 Minecraft
12 Braid


Output:

2 Portal 2,0 Minecraft,15 Braid
2 Portal 2,4 Minecraft,8 Braid
2 Portal 2,8 Minecraft,1 Braid
5 Portal 2,3 Minecraft,1 Braid


Python, 356 characters

I took a slight hit for reading from the command line:

from sys import argv
x=int(argv)
t=argv[3::2]
c=argv[2::2]
n=len(t)
s=*n
d=1
g=1
while d:
i=0
s[i]+=1
while int(c[i])*s[i]>x:
s[i]=0
if i+1>=n:
d=0
else:
i+=1
s[i]+=1
if d and sum(map(lambda y:int(c[y])*s[y],range(n)))==x:
g=0
print zip(t, s)
if g:print"X"


Example input:

python stuff.py 1505 215 'Mixed fruit' 275 'French fries' 335 'Side salad' 355 'Hot wings' 420 'Mozzarella sticks' 580 'Sampler plate'


Output:

[('Mixed fruit', 7), ('French fries', 0), ('Side salad', 0), ('Hot wings', 0), ('Mozzarella sticks', 0), ('Sampler plate', 0)]
[('Mixed fruit', 1), ('French fries', 0), ('Side salad', 0), ('Hot wings', 2), ('Mozzarella sticks', 0), ('Sampler plate', 1)]