Suppose S = {vi} and T = {ti} are "easy" sets of knapsak weight. Also, P and q are primes p > ?Si and q > ?ti. We can combine S and T into a signle set of knapsack weight as follows:

W = qs ? pT = {wi}= {qvi+pti}. Show:
1- all sums of the form ?eiwi are distinct. (ei= 0,1)
2- W is also an "easy" knapsack, that is solving ?eivi = n can be easily to solving ?eiwi= n1 and ?eiti= n2.

 

 

Posted Date: 4/1/2013 4:02:08 AM | Location : United States

Ask an Expert

Related Discussions:- Calculate signle set of knapsack weight, Assignment Help, Ask Question on Calculate signle set of knapsack weight, Get Answer, Expert's Help, Calculate signle set of knapsack weight Discussions

Write discussion on Calculate signle set of knapsack weight
Your posts are moderated

Write your message here..

Related Questions

Shares and divident, A man invest ?13500 partly in shares paying 6% at ?140... A man invest ?13500 partly in shares paying 6% at ?140 and partly in 5% at 125.If he is tolal income is 560, how much has he invested in each?

Sketch several trajectories for the system, Sketch several trajectories for... Sketch several trajectories for the system, x 1 ' = x 1 + 2x 2                                                                                x 2 ' = 3x 1 + 2x 2

Equivalence relation, a) Let V = f1, 2, :::, 7g and define R on V by xRy if... a) Let V = f1, 2, :::, 7g and define R on V by xRy iff x -  y is a multiple of 3. You should know by now that R is an equivalence relation on V . Suppose that this is so. Explain t

Initial recognition of the financial instruments, Grimm plc (Grimm) has the... Grimm plc (Grimm) has the following transactions: a) On 1 st January 2010, Grimm issued 400,000 convertible £1 6% debentures for £600,000.  The professional fees associated wit

Velocity of derivation, Velocity : Recall that it can be thought of as sp... Velocity : Recall that it can be thought of as special case of the rate of change interpretation. If the situation of an object is specified by f(t ) after t units of time the vel

Find the sides of the two squares, The sum of areas of two squares is 468m ... The sum of areas of two squares is 468m 2  If the difference of their perimeters is 24cm, find the sides of the two squares. Ans:    Let the side of the larger square be x .

Mathematics is all around us-mathematics- in our lives, Mathematics Is All ... Mathematics Is All Around Us :  What is the first thing you do when you get up? Make yourself a nice cup of tea or coffee? If so, then you're using mathematics! Do you agree? Cons

Vectors, A triangle has vertices A (-1, 3, 4) B (3, -1, 1) and C (5, 1, 1).... A triangle has vertices A (-1, 3, 4) B (3, -1, 1) and C (5, 1, 1). The area of ABC is a) 30.1 b) 82.1 c) 9.1 d) 52.1

Intigrations, intigration techiniqes intigration techiniqes

Illustrate child ability to perform a math task, Give an example to illustr... Give an example to illustrate how language incompetence can interfere with a child's ability to perform a task. While setting up a classification activity, a teacher gave the ch