programming problems from competition..
i am competing in a programming competition, for which while practicing i cannot solve these probs. These are not my HOMEWORK and i've tried a whole lot to solve them. But couldn't....
Plz. help....any help would b great appreciated...i don't want the complete solutions just simple ideas/algorithms will do....
1. BIN PACKING PROBLEM
Suppose u have a number of boxes each of which hold total weight W and items i1,i2,i3.....,in which weigh w1,w2,w3,....,wn...The objective is 2 pack all items without placing any more weight in any box than its capacity and using as few boxes as possible. e.g. if W=5 and the items have weights 2,2,3,3 then we can solve the problem with two boxes.
Write a program to which, given the Weight capacity W of the boxes and the weights of the individual items, determines the min. number of boxes in which the items can fit.
2. AMICABLE NUMBER
A pair of numbers is said to be amicable if the sum of the some divisors of each of the numbers (excluding the number itself) is equal to the other number.
Plz note that all possible divisors may not be considered for making up the sum. For e.g. in the case of 12 and 16, the divisors of 12 are 1,2,3,4,6 whose sum is 16. Moreover the divisors of 16 are 1,2,4,8 of which the sum of 4 & 8 alone gives 12 (1,2 need not be considered). Hence, amicability b/w two numbers exists if any m divisors out of the possible n divisors add up to the other number.
3. SPANNING TREE PROBLEM
A tree is an acyclic (without circuits) connected graph. A connected graph is the one in which every node is connected to at least one other node.
A spanning tree is in which every node is connected to only one other node.
Write a program that given a graph determines the number of nodes that can b removed to convert it into a spanning tree...
First take the total number of nodes as input. Then take the input in the form of comma-separated list representing a node and the nodes it is connected to
e.g. 1,3,4,5 means that node 1 is connected to nodes 3,4 & 5
THANX A WHOLE LOT IN ADVANCE...