Problema rucsacului

Cerință:

Se dă o multime formată din N obiecte, fiecare fiind caracterizat de o greutate și un profit. Să se găsească o submulțime de obiecte astfel încât suma profiturilor lor sa fie maximă, iar suma greutăților lor să nu depășească o valoare G.

​

Rezolvare:

Soluția optimă are la bază următoarea dinamică: pentru un i fixat se calculează Dpj = profitul maxim care se poate obține având un rucsac de capacitate j, G ≥ j ≥ W[ i ]. Recurența este următoarea: Dp[ j ] = max(Dp[ j ] – W[ i ] + P[ i ], Dp[ j ]). Complexitatea este O(N*G) timp și O(G) memorie.

​

#include <iostream>

#include <fstream>

using namespace std;

const int maxn = 5e3 + 5;

const int maxg = 1e4 + 5;

int P[maxn], W[maxn], Dp[maxg];

int main() {

    int n, i, j, G, ans = 0;

    cin >> n >> G;

    for (i = 1; i <= n; i++) {

        cin >> W[i] >> P[i];

    }

    for (i = 1; i <= n; i++) {

        for (j = G; j >= W[i]; j--) {

            if (Dp[j] < Dp[j - W[i]] + P[i]) {

                Dp[j] = Dp[j - W[i]] + P[i];

                if (Dp[j] > ans) {

                    ans = Dp[j];

                }

            }

        }

    }

    cout << ans << "\n";

    return 0;

}