Solve the knapsack problem

Question

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[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 1

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"}]

Answer 2

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')]

Answer 3

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[0]?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

Answer 4

Python, 356 characters

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

from sys import argv
x=int(argv[1])
t=argv[3::2]
c=argv[2::2]
n=len(t)
s=[0]*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)]

Answer 5

JavaScript (V8), 225 bytes

(t,k,l,a=d=0)=>[...Array(t+1)].flatMap((_,j)=>[...Array(k[L="length"]**j)].map((_,i)=>eval("r=[];while(j-r[L])r.push(i%k[L]),i=i/k[L]|0;r")).filter(p=>(a=m=d=0,p.map(i=>(a+=k[i],d|=i<m,m=i)),a==t&&!d)).map(p=>p.map(i=>l[i])))

I had a bunch of really neat ideas for how to golf this but they ended up not working.