Como distribuir um número de elementos em um bucket para que fique dentro de um intervalo?

Question

Como distribuir um número de elementos em um bucket para que fique dentro de um intervalo?

#1 resposta do (2 votos)
#2 resposta do (1 votos)

5

Eu tenho 50 elementos n1, n2, n3, ..., n50 e um número limitado de baldes, digamos, 5 baldes e cada balde pode conter um intervalo de, digamos 100 a 150 apenas (o que não é senão a soma de os elementos desse balde), mas não menos de 100, nem mais de 150.

Qual algoritmo é mais adequado para resolver este problema, de forma que todos os 5 baldes sejam usados e todos os elementos (n1, n2, n3, ...) também sejam usados?

Se um bucket não puder ser usado ou se algum elemento tiver que ser omitido, o algoritmo deve retornar "InvalidConditionsFound".

Eu experimentei o Knapsack, que lhe dá uma combinação mais próxima de um determinado número, mas como obtê-lo dentro de um intervalo e também garantir que ele escolha sabiamente, de modo que todos os baldes estejam sendo preenchidos. cheio e o outro balde está apenas em, digamos 50?

java algorithms optimization

por Argho Chatterjee 06.10.2015 / 12:29

fonte

2 respostas

Tags java algorithms optimization

Qual é a maneira mais genérica de fornecer uma quantidade variável de saídas de uma função Rust? Design orientado a objeto para criar imagens em Python

score 2 · Answer 1

50 elementos x 5 baldes? Esses são números pequenos. Uma heurística de retrocesso de força bruta provavelmente funcionará. Classifique-os, adicione elementos aos baldes tentando manter os totais do balde iguais. Se você não obtiver uma solução em um passo, retroceda.

Uma vez, usei um processo semelhante para atribuir paletes de mercadorias a caminhões. O objetivo era minimizar o número de caminhões necessários para conter todos os paletes. Cada caminhão tinha uma capacidade máxima de peso (e um limite de paletes). Primeiro eu segui Best-Fit-First para carregar o número mínimo teórico de caminhões. Se eu tivesse paletes sobrando, encontrei os dois caminhões mais vazios e fiz uma força bruta reembalando para ver se conseguia espremer mais um palete. Este algoritmo embalou com sucesso 200 paletes com um peso total de 499.000 libras em 10 caminhões com uma capacidade de 50.000 libras cada.

score 1 · Answer 2

Você tem K buckets, atualmente cinco.

Classifique seus valores de entrada positivos e encontre a soma deles, s . Verifique se 100 × K ≤ s ≤ 150 × K ou aborta de uma só vez.

Processar avidamente cada valor de entrada, do maior para o menor, e atribuí-lo a um intervalo. Em uma variante do algoritmo, deterministicamente, atribua-o ao bucket atualmente mais leve. Em uma variante mais cara, atribua-a aleatoriamente a um intervalo elegível e esteja preparado para alguma quantidade de retrocessos ou novas tentativas se as coisas não funcionarem inicialmente.