3
\$\begingroup\$

Knapsack Problem

(Actually, this is a subset of real knapsack problem.... - there's nothing to optimize!)

The knapsack problem is:

Given positive integers a_1, a_2, ..., and an integer S, find non-negative integers u_1, u_2, ... satisfies \sum_{i} a_i u_i = S

... or in (my bad) English...

Suppose you have many stuffs which weights a_1, a_2, ..., 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 a_1, a_2, ..., and names of each stuffs.

Stuffs' name may contain [a-zA-Z0-9 _] (alphanumeric + _ + space).

You may assume that the input is correct, a_1, a_2, ... are positive, and S is non-negative.

For example, consider this pseudo-real world situation, where a man orders appetizers worth exactly $15.05:

First cell of xkcd.com/287

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Matthew Read Sep 28 '11 at 20:15
  • \$\begingroup\$ @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. \$\endgroup\$ – JiminP Sep 28 '11 at 22:04
  • \$\begingroup\$ Wait, does Mac use \r? \$\endgroup\$ – JiminP Sep 28 '11 at 22:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Matthew Read Sep 28 '11 at 22:07
  • 5
    \$\begingroup\$ 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/… \$\endgroup\$ – J B Sep 28 '11 at 22:30
1
\$\begingroup\$

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')]
\$\endgroup\$
3
\$\begingroup\$

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"}]
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.