# 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[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. • 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. Sep 28, 2011 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. Sep 28, 2011 at 22:04 • Wait, does Mac use \r? Sep 28, 2011 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. Sep 28, 2011 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, 2011 at 22:30 ## 5 Answers # 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"}]  ## 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')]  ### 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


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


# 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.