Problema da Mochila

A empresa de transportes Poxim Tech está tornando as entregas de encomendas de última milha mais eficientes e rápidas através da maximização do valor total do frete e levando em consideração as características de cada tipo de veículo Para codificação das placas de trânsito dos veículos e dos códigos de rastreamento dos pacotes são utilizados os símbolos L e N que representam letras maiúsculas e números respectivamente As unidades utilizadas para peso é quilo kg valor é reais R e volume é litro l Cada veículo é identificado pela sua placa de trânsito nos formatos LLLNNNN ou LLLNLNN além da sua capacidade máxima de carga peso e volume Os pacotes possuem um código de rastreamento descrito no padrão LLNNNNNNNNNLL juntamente com informações sobre o valor peso e volume Formato do arquivo de entrada n Placa0 Peso0 Volume0 Placan1 Peson1 Volumen1 m Código0 Valor0 Peso0 Volume0 Códigom1 Valorm1 Pesom1 Volumem1 2 AAA1234 50 100 BBBSC67 2000 12000 5 AB111222333CD 4999 2 1 EF444555666GH 500001 1234 7000 IJ777888999KL 100 49 10 MN0001112220P 6501 3 125 QR333444555ST 20001 13 4875 Formato do arquivo de saída Para cada veículo é gerada uma sequência de carregamento dos pacotes que maximizam o valor transportado sem exceder a capacidade de carga AAA1234R1000049KG9810L10 IJ777888999KL BBBSC67R5265031250KG6312000L100 EF444555666GH MN0001112220P QR333444555ST PENDENTER49992KG1L AB111222333CD