Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("rucsac.in");
- ofstream fout("rucsac.out");
- int N, G, k = 1;
- int p[10001], g[10001], dp[2][10001];
- int main()
- {
- fin >> N >> G; // citesc numarul de obiecte si greutatea maxima
- for(int i = 1; i <= N; i++)
- fin >> g[i] >> p[i]; // citesc greutatea si profitul obiectului
- for(int i = 1; i <= N; i++) // parcurg fiecare obiect
- {
- for(int j = 1; j <= G; j++) //
- if(j - g[i] >= 0)// daca obiectul incape in ghiozdan
- dp[k][j] = max(dp[1-k][j], dp[1-k][j - g[i]] + p[i]), fout << dp[k][j] << ' ';// profitul maxim va fi cel de deasupra sau profitul obiectului plus profitul celorlalte obiecte
- else
- dp[k][j] = dp[1-k][j]; // altfel profitul maxim este cel cu o linie mai sus
- k = 1 - k, fout << '\n';
- }
- fout << dp[1-k][G];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement