Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2019-10-14 14:08:50.
Revizia anterioară   Revizia următoare  

Soluţia problemei Shoturi

Soluţie backtracking - 10 puncte

Generăm toate variantele posibile ale vectorului x pentru care 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 O(K^N) 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 din primele i substanţe interzise sucuri j shoturi păhărele.