Optimization problem with sets
-
Hello! I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices. I want to take the sum of the items that equal to number k, and the price is minimal. The example: A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1)) So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11. Any idea? Thanks!
-
Hello! I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices. I want to take the sum of the items that equal to number k, and the price is minimal. The example: A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1)) So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11. Any idea? Thanks!
The problem and your notation aren't clear.
-
Hello! I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices. I want to take the sum of the items that equal to number k, and the price is minimal. The example: A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1)) So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11. Any idea? Thanks!
This sounds like a homework problem, and if so, you should consult with your instructor. As the other poster had said, your problem is not entirely clear, may want to rephrase it.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon "Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
-
Hello! I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices. I want to take the sum of the items that equal to number k, and the price is minimal. The example: A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1)) So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11. Any idea? Thanks!
Your problem sounds like the knapsack problem. 4^n just acts as item-id (given in this peculiar notation to confuse) while k is the capacity of the knapsack. Its easy to solve this problem using the method of dynamic programming. Brute-force approaches which rely on generating combination also exist.