Optimização de valores

[HQuintas]

Boas...

Como faço para obter um grupo de valores que somados se aproximem o mais possível, mas não ultrapasse um determinado valor.

Ou seja, tenho estes valores: (estão armazenados numa tabela ou numa lista)

1500;1500;1200;1200;1100;1100;1100;1100;1000;1000;900;900;600;600;600;600;400;400;400;400;

Quero somar os valores e que a soma fique o mais aproximado de 3000, mas não ultrapasse.

Exemplo:

1500+1500=3000

1200+1200+600=3000

1100+1100+400+400=3000

1100+1100+400+400=3000

1000+1000+600=2600

900+900+600+600=3000

Alguém tem alguma ideia como possa fazer isto ?

Obrigado

[He B TeMy]

Dim toAdd As Integer = 0
 Dim list As New List(Of Integer)() From {1500, 1500, 1200, 1200, 1100, 1100, 1100, 1100, 1000, 1000, 900, 900, 600, 600, 600, 600, 400, 400, 400, 400}

 For i As Integer = 0 To list.Count - 1
	 toAdd += list(i)
	 If toAdd <= (3000 - list(i)) Then
		 If i + 1 = list.Count Then
			 'Se for o último valor exibimos o nr e terminamos o loop.
			 Debug.WriteLine(toAdd.ToString())
			 Exit For
		 End If
		 Continue For
	 Else
		 Debug.WriteLine(toAdd.ToString())
		 toAdd = 0
	 End If
 Next

Vê se ajuda, basicamente isto faz as somas todas possíveis e exibe-as no Debug.

Atenção que só funciona se os valores estiverem ordenados do maior para o menor.

Espero que ajude.

Edited January 23, 2016 by ribeiro55

[HQuintas]

Boas

Infelizmente não é isso que pretendo.Já tenho implementada uma rotina idêntica a essa, em que ordeno os valores e vai preenchendo desde que não ultrapasse o valor total.

Em que dá um resultado:

1500+1500=3000

1200+1200+600=3000

1100+1100+600=2800

1100+1100+600=2800

1000+1000+900=2900

900+600+400+400+400=2700

400=400

Mas eu pretendo o resultado, assim:

1500+1500=3000

1200+1200+600=3000

1100+1100+400+400=3000

1100+1100+400+400=3000

1000+1000+600=2600

900+900+600+600=3000

Como podem observar tem menos uma parcela. Em que faz uma optimização dos valores as somar.

Obrigado, na mesma. Se tem mais alguma ideia como fazer isto agradecia imenso.

[He B TeMy]

Com os números que puseste acima eu recebo isto de output:

3000
2400
2200
2200
2900
2700
2200

Se você quer da maneira que disse para todos os valores isso vai ser mais complicado porque vais ter de fazer loop várias vezes sobre a colecção, têm de ser mesmo assim?

[HQuintas]

Sim tem que ser mesmo assim, tenho que conseguir.

Se alguém poder dar uma ajuda agradeço.