Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2019-10-14 14:15:33.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Soluţia problemei Shoturi
Soluţie backtracking - 10 puncte
Generăm toate variantele posibile ale vectorului 
pentru care ![x[1] + x[2] + ... + x[N] = K](https://www.infoarena.ro/static/images/latex/506d3abf4add17c6f8d9d61040f832f4_3.5pt.gif "x[1] + x[2] + ... + x[N] = K")
. Această soluţie obţine 0 sau 10 puncte în funcţie de implementarea backtrackingului, care ar avea complexitatea 
amortizat.
Soluţie N3 - 50 puncte
Această soluţie presupune tehnica programării dinamice. Vom folosi matricea dp[n][k], pentru care:
dp[i][j] = care este suma potenţelor tuturor amestecurilor posibile ingerând j shoturi păhărele din primele i substanţe interzise.
De aici deducem recurenţa: ![\displaystyle \dp[i][j]=sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]](https://www.infoarena.ro/static/images/latex/1d0875e417cf3902ada9d29d2086e65d_3.6666pt.gif "\displaystyle \dp[i][j]=sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]")
