Dado um conjunto de itens, cada um com um peso e um valor, determine o número de cada item a ser incluído em uma coleção, para que o peso total seja menor ou igual a um determinado limite e o valor total seja o maior possível.

Wikipedia para mais informações

Por exemplo, você pode receber um peso máximo de 15 e objetos com valor / massa como [5,2], [7,4] [1,1]e você produziria [7,0,1]7 [5 <value>, 2 <mass>]objetos e 1 [1 <value>, 1 <mass>]objeto para uma pontuação de 36.

Regras

A entrada pode ser obtida em qualquer formato razoável

A saída também é um formato flexível,

Você não pode usar bibliotecas que não são padrão. Se você tem que instalar ou baixar qualquer biblioteca de usá-lo separar-se da configuração inicial, então é não permitido

Objetos podem ter massa e valor negativos (ie -1, -1)

Respostas ideais necessárias

Ganhando

O código mais curto vence

Massa e valor negativos?

Esta é uma parte essencial deste desafio. Digamos que você tenha um objeto com itens (massa, valor) como [4,3],[-1,-1]e uma bolsa com capacidade de 15. Você pode colocar 3 dos primeiros e marcar 9 ou colocar 4 dos primeiros e um dos -1, -1 objeto para uma pontuação de 11.

Pitão, 18 bytes

h.MshMZfghQseMTy*F

Saída como uma lista de pares [valor, peso]. Terrivelmente ineficiente, mas é NP-completo.
Experimente aqui

Explicação

h.MshMZfghQseMTy*F
               y*FQ  Get all sets with up to <capacity> of each item.
       fghQseMT      Choose the sets whose total weight fits in the bag.
 .MshMZ              Choose those with the highest value.
h                    Take the first.