解背包问题

Question

背包问题

(实际上，这是真实背包问题的子集.-没有什么需要优化的！)

背包问题是：

给定正整数

，和一个整数S，找到非负整数。

满足感

..。或者用(我糟糕的)英语..。

假设你有很多东西可以称重

，找到那些重量为S的东西的配置。

问题

找到所有的配置，这些信息是由输入提供的。

输入

您可以创建自己的格式，但是您应该允许用户输入内容的总和(S)，内容的权重。

，以及每件东西的名称。

内容的名称可能包含[a-zA-Z0-9 _] (字母数字+ _ +空格)。

您可以假设输入是正确的，

是积极的，而S是非消极的.

例如，考虑一下这个虚拟现实世界的情况，一个男人点了价值15.05美元的开胃菜：

一项可能的投入是：

1505
215 Mixed fruit
275 French fries
335 Side salad
355 Hot wings
420 Mozzarella sticks
580 Sampler plate

输出

打印所有可能的配置(没有相同的配置，每一行一个配置，每一行包含一对内容和名称)。

零数量的东西可以省略。

如果没有配置，只需打印X即可。

示例

输入和输出格式(和顺序)可以不同。

这是我粗略编写的JS代码：

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

输入

1505/215 Mixed fruit/275 French fries/335 Side salad/355 Hot wings/420 Mozzarella sticks/580 Sampler plate

输出

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, 

输入

5/1 A/1 B/1 C

输出

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, 

输入

10/20 A/11 B

输出

X

输入

250/35 Portal 2/21 Minecraft/12 Braid

输出

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, 

输入

250/33 Portal 2/21 Minecraft/12 Braid

输出

X

获胜者

因为这是代码高尔夫游戏，以最短代码的人获胜。

如果两个代码的长度相同，那么得票率最高的代码就会获胜。

Answer 1

Python，185个字符

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'

使用这样的输入运行它：

echo "[1505,[215,275,335,355,420,580],['MF','FF','SS','HW','MS','SP']]" | ./knapsack.py

上面写着S，一份费用清单，一份与这些费用相对应的项目名称清单。

它输出项目计数和项目名称的列表：

[(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 2

Mathematica，59 chars

Tally/@IntegerPartitions[#1,All,#2/._[x_,_]->x]/.#2/.{}->X&

用

%[1505, {215 -> "MF", 275 -> "FF", 335 -> "SS", 355 -> "HW", 420 -> "MS", 580 -> "SP"}]

Answer 3

Ruby，136个字符

a,*b=*A2lt;
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

必须在STDIN上输入，其中一行表示总量，然后每项输入一行(权重，后面是空格，后面是名称)。

示例输入：

250
35 Portal 2
21 Minecraft
12 Braid

输出：

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