Szczegółowe omówienie zadania High Profit Only:

Link do powyższego omówienia zadania High Profit Only:
https://youtu.be/3hOA-hfPmOU?t=1951

Link do treści zadania High Profit Only:
https://szkopul.edu.pl/problemset/problem/hpo/site

–
Zadanie High Profit Only jest zadaniem które pokazuje moc problemu plecakowego:
https://youtu.be/3hOA-hfPmOU?t=19

–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

====
Kod C++ programu High Profit Only, który jest omówiony w powyższym filmie i który otrzymuje 100%
–

#include <bits/stdc++.h>
using namespace std;

const int MAX_MONEY = 30010;
long long int max_profit[MAX_MONEY];

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int money, number_of_projects;
 int investment, profit;
 int i, project, act_money;
 long long int solution;

 cin >> money;
 cin >> number_of_projects;

 for (i=1; i<=MAX_MONEY; ++i)
    max_profit[i] = -1;

 for (project=1; project<=number_of_projects; ++project) {
    cin >> investment;
    cin >> profit;
    for (act_money=money-investment; act_money>=0; --act_money) {
       if (max_profit[act_money] == -1)
          continue;
       max_profit[act_money+investment] = max (max_profit[act_money+investment], max_profit[act_money]+profit);
    }
 }

 solution=0;
 for (i=0; i<=money; ++i)
    solution = max(solution,max_profit[i]);

 cout << solution;

 return 0;
}