O problema da mochila é descrito a seguir: Você tem uma mochila com capacidade total para C quilos;

Você tem N objetos que quer levar na mochila;
Cada objeto do tipo i tem um peso P_i;
Cada objeto do tipo i tem um valor V_i;

Seu objetivo é conseguir levar na mochila o maior valor possível, sem estourar a capacidade dela. Por exemplo:

Capacidade da mochila = 70

Canivete (valor 10) (peso 10)
Pendrive (valor 200) (peso 5)
Livro (valor 400) (peso 40)
Lata de sardinha (valor 20) (peso 20)
Celular (valor 500) (peso 30)

Você poderia levar:

1 livro (v=400 p=40)
1 lata de sardinha (v=20 p=20)
1 canivete (v=10 p=10)

Total do peso: 70. Total do valor: 430 Ou você poderia levar:

2 celulares (v=1000, p=60)
2 pendrives (v=400, p=10)

Total do peso: 70. Total do valor: 1400.

Você deve fazer um programa que leia de um arquivo:

A capacidade da mochila
Uma lista de tipos de objeto, um por linha, com nome, peso e valor.

O exemplo que demos acima poderia ser colocado num arquivo como segue:

-----
70
canivete 10 10
pendrive 200 5
livro 400 40 
sardinha 20 20
celular 500 30 
-----

Depois de ler o arquivo, seu programa deve gerar várias soluções aleatóreas para o problema (por exemplo, 500 soluções) e depois mostrar a melhor solução encontrada.