How does this solution of the subset sum problem‍​​ work?

Re: need help with polynomials assignment

• QUESTION: Hi Zlatko, Check out my code now, I think the polynomial printing works now. I used all if statements to do it. Thanks, Mike using namespace std; class Polynomial { public: Polynomial(int t1 = 0, int t2 = 0, int t3 = 0, int t4 = 0, int t5 = 0); Polynomial calcSum(const Polynomial& p2); Polynomial calcDifference(const Polynomial& p2); Polynomial calcProduct(const Polynomial& p2); void printPolynomial(); private: int c4, c3, c2, c1, c0; }; Polynomial :: Polynomial(int t1, int t2, int t3, int t4, int t5) { c4 = t1; c3 = t2; c2 = t3; c1 = t4; c0 = t5; } void Polynomial :: printPolynomial() { cout = 0; --exp) { if(coef[exp] == 1) cout 0 && coef[exp] != 1 && (exp != 1 && exp != 0 && exp != 4)) cout 0 && coef[exp] != 1 && (exp == 1 || exp == 0)) cout 0 && coef[exp] != 1 && exp == 4) cout Polynomial sum; sum.c4 = c4 + p2.c4; sum.c3 = c3 + p2.c3; sum.c2 = c2 + p2.c2; sum.c1 = c1 + p2.c1; sum.c0 = c0 + p2.c0; return sum; } Polynomial Polynomial :: calcDifference(const Polynomial& p2) { Polynomial difference; difference.c4 = c4 - p2.c4; difference.c3 = c3 - p2.c3; difference.c2 = c2 - p2.c2; difference.c1 = c1 - p2.c1; difference.c0 = c0 - p2.c0; return difference; } Polynomial Polynomial:: calcProduct(const Polynomial& p2) { Polynomial product; product.c4 = c2*p2.c2; product.c3 = c2*p2.c1 + c1*p2.c2; product.c2 = c2*p2.c0 + c1*p2.c1 + c0*p2.c2; product.c1 = c1*p2.c0 + c0*p2.c1; product.c0 = c0*p2.c0; return product; } int main() { Polynomial p1(1, 2, 3, -4, 5); Polynomial p2(-2, 3, -5, 6, 9); Polynomial p3(0, 0, 1, 2, 3); Polynomial p4(0, 0, 1, 2, 3); cout cout /* first is a flag. It is useful to know if the first coefficient has been printed out. Why ? Because if you're working on the first coefficient, and it is positive, you don't want the leading "+" being printed. Also, if you get to the end of the print function and first is still true, then it means that nothing has been printed so far */ bool first = true; /* Work from the highest exponent to the lowest. Notice that the exp variable can also be used to print the number after the exponent sign "^" */ for(int exp = 4; exp >= 0; --exp) { if (coef[exp] != 0) // don't print 0x { if (coef[exp] == -1 && exp != 0) { /* for -1, just print -, not -1, so we get -x instead of -1x, BUT, if the exponent is 0, then DO print -1. That is done at line AAA */ cout 0) { if (!first) { /* DO print leading + sign on a postitive coefficient, unless it is the first coefficient */ cout // finally print the x for non zero exponents if (exp >= 1) cout = 2) cout } ---------- FOLLOW-UP ---------- QUESTION: Hi Zlatko, I think it really is a good idea if you do look at what someone else did, especially if there are shorter / more intuitive ways of solving the same problem. Sometimes I feel that there are things that I did not think of, and sometimes those little things make all the difference when it's actually a really simple thing that you could have thought of but you just didn't for whatever the reason may be. So thank you very much for your help. I believe your way is good too, maybe a bit better strategy than what I attempted, but both seem logical so it's fine I guess Here is my code once more, I believe it works now fine. The bug that you've found, I tested and that combination does work fine. using namespace std; class Polynomial { public: Polynomial(int t1= 0, int t2= 0, int t3= 0, int t4= 0, int t5= 0); Polynomial calcSum(const Polynomial& p2); Polynomial calcDifference(const Polynomial& p2); Polynomial calcProduct(const Polynomial& p2); void printPolynomial(); private: int c4, c3, c2, c1, c0; }; Polynomial :: Polynomial(int t1, int t2, int t3, int t4, int t5) { c4 = t1; c3 = t2; c2 = t3; c1 = t4; c0 = t5; } void Polynomial :: printPolynomial() { cout = 0; --exp) { if(coef[exp]==1) cout cout 0 && exp==0) cout if(coef[4]==0 && coef[3]==0 && coef[2]==0 && coef[1]==0 && coef[0]==0 && exp==4) cout if(coef[exp]>0 && coef[exp]!=1 && (exp!=1 && exp!=0 && exp!=4)) cout 0 && coef[exp]!=1 && (exp==1)) cout else if(coef[exp]>0 && coef[exp]!=1 && exp==4) cout if(coef[exp] else if(coef[exp] cout } Polynomial Polynomial :: calcSum(const Polynomial& p2) { Polynomial sum; sum.c4 = c4 + p2.c4; sum.c3 = c3 + p2.c3; sum.c2 = c2 + p2.c2; sum.c1 = c1 + p2.c1; sum.c0 = c0 + p2.c0; return sum; } Polynomial Polynomial :: calcDifference(const Polynomial& p2) { Polynomial difference; difference.c4 = c4 - p2.c4; difference.c3 = c3 - p2.c3; difference.c2 = c2 - p2.c2; difference.c1 = c1 - p2.c1; difference.c0 = c0 - p2.c0; return difference; } Polynomial Polynomial:: calcProduct(const Polynomial& p2) { Polynomial product; product.c4 = c2*p2.c2; product.c3 = c2*p2.c1 + c1*p2.c2; product.c2 = c2*p2.c0 + c1*p2.c1 + c0*p2.c2; product.c1 = c1*p2.c0 + c0*p2.c1; product.c0 = c0*p2.c0; return product; } int main() { Polynomial p1(0, 0, 0, 0, -2); Polynomial p2(-2, 3, -5, 6, 9); Polynomial p3(0, 0, 1, 2, 3); Polynomial p4(0, 0, 1, 2, 3); cout Polynomial sum = p1.calcSum(p2); cout Polynomial difference = p1.calcDifference(p2); cout cout Polynomial product = p3.calcProduct(p4); cout }

• Answer:

  Hi Mike Ok, I found 3 errors, and I made a minor change to fix them. The following are errors, because they are mathematically incorrect. [Coeff 0 0 0 0 1] x^0+1 [Coeff 0 0 0 0 -1] -x^0-1 [Coeff 1 1 1 1 1] x^4x^3x^2x^1x^0+1 My 3 fixes are commented in the code below. Just look for zm void Polynomial :: printPolynomial() { cout int coef[5] = {c0, c1, c2, c3, c4}; for(int exp = 4; exp >= 0; --exp) { if(exp != 0 && coef[exp]==1) // zm added exp != 0 { cout if(exp != 0 && coef[exp]==-1) // zm added exp != 0 cout if(coef[exp]>0 && exp==0) cout if(coef[4]==0 && coef[3]==0 && coef[2]==0 && coef[1]==0 && coef[0]==0 && exp==4) cout if(coef[exp]>0 && coef[exp]!=1 && (exp!=1 && exp!=0 && exp!=4)) cout if(coef[exp]>0 && coef[exp]!=1 && (exp==1)) cout 0 && coef[exp]!=1 && exp==4) cout if(coef[exp] } With the fixes, the polynomials all print mathematically correct, although there are some awkward constructs like leading plus signs and x^1, but that's OK. Mathematically it is correct. For your reference, here is the full test output. My eyes glaze over from looking at it. You can see that programming is all about the details. [Coeff 0 0 0 0 0] 0 [Coeff 0 0 0 0 1] +1 [Coeff 0 0 0 1 0] +x^1 [Coeff 0 0 1 0 0] +x^2 [Coeff 0 1 0 0 0] +x^3 [Coeff 1 0 0 0 0] +x^4 [Coeff 0 0 0 0 -1] -1 [Coeff 0 0 0 -1 0] -x^1 [Coeff 0 0 -1 0 0] -x^2 [Coeff 0 -1 0 0 0] -x^3 [Coeff -1 0 0 0 0] -x^4 [Coeff 0 0 0 0 2] +2 [Coeff 0 0 0 2 0] +2x [Coeff 0 0 2 0 0] +2x^2 [Coeff 0 2 0 0 0] +2x^3 [Coeff 2 0 0 0 0] 2x^4 [Coeff 0 0 0 0 -2] -2 [Coeff 0 0 0 -2 0] -2x [Coeff 0 0 -2 0 0] -2x^2 [Coeff 0 -2 0 0 0] -2x^3 [Coeff -2 0 0 0 0] -2x^4 [Coeff 1 1 1 1 1] +x^4+x^3+x^2+x^1+1 [Coeff 1 1 1 1 0] +x^4+x^3+x^2+x^1 [Coeff 1 1 1 0 0] +x^4+x^3+x^2 [Coeff 1 1 0 0 0] +x^4+x^3 [Coeff 1 0 0 0 0] +x^4 [Coeff 0 0 0 0 1] +1 [Coeff 0 0 0 1 1] +x^1+1 [Coeff 0 0 1 1 1] +x^2+x^1+1 [Coeff 0 1 1 1 1] +x^3+x^2+x^1+1 [Coeff -1 -1 -1 -1 -1] -x^4-x^3-x^2-x^1-1 [Coeff -1 -1 -1 -1 0] -x^4-x^3-x^2-x^1 [Coeff -1 -1 -1 0 0] -x^4-x^3-x^2 [Coeff -1 -1 0 0 0] -x^4-x^3 [Coeff -1 0 0 0 0] -x^4 [Coeff 0 0 0 0 -1] -1 [Coeff 0 0 0 -1 -1] -x^1-1 [Coeff 0 0 -1 -1 -1] -x^2-x^1-1 [Coeff 0 -1 -1 -1 -1] -x^3-x^2-x^1-1 [Coeff 2 2 2 2 2] 2x^4+2x^3+2x^2+2x+2 [Coeff 2 2 2 2 0] 2x^4+2x^3+2x^2+2x [Coeff 2 2 2 0 0] 2x^4+2x^3+2x^2 [Coeff 2 2 0 0 0] 2x^4+2x^3 [Coeff 2 0 0 0 0] 2x^4 [Coeff 0 0 0 0 2] +2 [Coeff 0 0 0 2 2] +2x+2 [Coeff 0 0 2 2 2] +2x^2+2x+2 [Coeff 0 2 2 2 2] +2x^3+2x^2+2x+2 [Coeff -2 -2 -2 -2 -2] -2x^4-2x^3-2x^2-2x-2 [Coeff -2 -2 -2 -2 0] -2x^4-2x^3-2x^2-2x [Coeff -2 -2 -2 0 0] -2x^4-2x^3-2x^2 [Coeff -2 -2 0 0 0] -2x^4-2x^3 [Coeff -2 0 0 0 0] -2x^4 [Coeff 0 0 0 0 -2] -2 [Coeff 0 0 0 -2 -2] -2x-2 [Coeff 0 0 -2 -2 -2] -2x^2-2x-2 [Coeff 0 -2 -2 -2 -2] -2x^3-2x^2-2x-2 And here is the full test code which you can call from main if you want to play with it further. void PolynomialPrintTest() { Polynomial().printPolynomial(); Polynomial(0, 0, 0, 0, 1).printPolynomial(); Polynomial(0, 0, 0, 1, 0).printPolynomial(); Polynomial(0, 0, 1, 0, 0).printPolynomial(); Polynomial(0, 1, 0, 0, 0).printPolynomial(); Polynomial(1, 0, 0, 0, 0).printPolynomial(); Polynomial(0, 0, 0, 0, -1).printPolynomial(); Polynomial(0, 0, 0, -1, 0).printPolynomial(); Polynomial(0, 0, -1, 0, 0).printPolynomial(); Polynomial(0, -1, 0, 0, 0).printPolynomial(); Polynomial(-1, 0, 0, 0, 0).printPolynomial(); Polynomial(0, 0, 0, 0, 2).printPolynomial(); Polynomial(0, 0, 0, 2, 0).printPolynomial(); Polynomial(0, 0, 2, 0, 0).printPolynomial(); Polynomial(0, 2, 0, 0, 0).printPolynomial(); Polynomial(2, 0, 0, 0, 0).printPolynomial(); Polynomial(0, 0, 0, 0, -2).printPolynomial(); Polynomial(0, 0, 0, -2, 0).printPolynomial(); Polynomial(0, 0, -2, 0, 0).printPolynomial(); Polynomial(0, -2, 0, 0, 0).printPolynomial(); Polynomial(-2, 0, 0, 0, 0).printPolynomial(); Polynomial(1, 1, 1, 1, 1).printPolynomial(); Polynomial(1, 1, 1, 1).printPolynomial(); Polynomial(1, 1, 1).printPolynomial(); Polynomial(1, 1).printPolynomial(); Polynomial(1).printPolynomial(); Polynomial(0, 0, 0, 0, 1).printPolynomial(); Polynomial(0, 0, 0, 1, 1).printPolynomial(); Polynomial(0, 0, 1, 1, 1).printPolynomial(); Polynomial(0, 1, 1, 1, 1).printPolynomial(); Polynomial(-1, -1, -1, -1, -1).printPolynomial(); Polynomial(-1, -1, -1, -1).printPolynomial(); Polynomial(-1, -1, -1).printPolynomial(); Polynomial(-1, -1).printPolynomial(); Polynomial(-1).printPolynomial(); Polynomial(0, 0, 0, 0, -1).printPolynomial(); Polynomial(0, 0, 0, -1, -1).printPolynomial(); Polynomial(0, 0, -1, -1, -1).printPolynomial(); Polynomial(0, -1, -1, -1, -1).printPolynomial(); Polynomial(2, 2, 2, 2, 2).printPolynomial(); Polynomial(2, 2, 2, 2).printPolynomial(); Polynomial(2, 2, 2).printPolynomial(); Polynomial(2, 2).printPolynomial(); Polynomial(2).printPolynomial(); Polynomial(0, 0, 0, 0, 2).printPolynomial(); Polynomial(0, 0, 0, 2, 2).printPolynomial(); Polynomial(0, 0, 2, 2, 2).printPolynomial(); Polynomial(0, 2, 2, 2, 2).printPolynomial(); Polynomial(-2, -2, -2, -2, -2).printPolynomial(); Polynomial(-2, -2, -2, -2).printPolynomial(); Polynomial(-2, -2, -2).printPolynomial(); Polynomial(-2, -2).printPolynomial(); Polynomial(-2).printPolynomial(); Polynomial(0, 0, 0, 0, -2).printPolynomial(); Polynomial(0, 0, 0, -2, -2).printPolynomial(); Polynomial(0, 0, -2, -2, -2).printPolynomial(); Polynomial(0, -2, -2, -2, -2).printPolynomial(); } I think you can put this baby to bed.