Possível combinação de problema de mochila e?

Tudo bem, visão rápida

Eu olhei para o problema da mochila

http://en.wikipedia.org/wiki/Knapsack_problem

e eu sei que é o que eu preciso para o meu projeto, mas a parte complicada do meu projeto seria que eu preciso de vários sacos dentro de um saco principal.

A grande mochila que contém todos os “sacos” só pode transportar x quantidade de “sacos” (digamos 9 por exemplo). Cada bolsa tem valores diferentes;

  • Peso
  • Custo
  • Tamanho
  • Capacidade

e assim por diante, todos esses valores são números inteiros. Vamos supor de 0 a 100.

O saco interno também será atribuído a um tipo, e só pode haver um desse tipo dentro do saco externo, embora a input do programa receba múltiplos do mesmo tipo.

Preciso atribuir um peso máximo que a sacola principal possa conter, e todas as outras propriedades das sacolas menores precisam ser agrupadas por valores ponderados.


Exemplo

Saco Exterior:

  • Pode segurar 9 sacos menores
  • Peso não mais que 98 [Dê ou leve 5 de cada lado]
  • Deve conter um de cada tipo, só pode conter um de cada tipo de cada vez.

Sacos Internos:

  • Custo, ponderado a 100%
  • Tamanho, ponderada em 67%
  • Capacidade, ponderada a 44%

O programa receberá uma input de várias malas e, em seguida, deverá elaborar combinações de Smaller Bags para entrar na sacola maior, haverá várias soluções dependendo da input e o programa produzirá as melhores soluções para mim.

Eu estou querendo saber o que vocês acham que a melhor maneira para eu abordar isso seria.

Eu vou programá-lo em Java ou C #. Eu adoraria programá-lo em PHP, mas temo que o algoritmo seja muito ineficiente para servidores web.

Obrigado por qualquer ajuda que você possa dar

-Zack

Ok, bem, a mochila é NP-hard, então eu tenho certeza que isso será NP-difícil também (se não fosse você poderia resolver mochila fazendo isso com apenas uma mochila). Então, para uma solução exatamente ótima, você provavelmente não será capaz de fazer buscas em todas as combinações. Então, o esboço do programa que você quer será como

for each possible combination do if current combination is better than best previous save current combination as best so far fi od 

e o tempo de execução será exponencial. Parece, no entanto, que você pode conseguir uma solução próxima com programação dinâmica .

Considere usar o Prolog para sua programação lógica. Existem múltiplas implementações, incluindo P # em mono (.NET). Há um pouco de curva de aprendizado, mas quando você se acostuma, é praticamente uma aliança própria para esse tipo de solução de problemas.

Espero que isto ajude. Felicidades!

link para P #