Cod sursa(job #3220981)
Utilizator | Diaconescu Victor Victor_9 | Data | 5 aprilie 2024 16:50:25 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
//rucsac
#include <bits/stdc++.h>
using namespace std;
const int nmax = 5005, gmax = 10005;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G, dp[gmax];
typedef struct poza{
int cost, prof;
}student;
student v[nmax];
int main(){
fin>>N>>G;
for(int i=1;i<=N;i++){
fin>>v[i].cost>>v[i].prof;
}
for(int j=1;j<=N;j++){
for(int i=G;i>=1;i--){
if(i - v[j].cost >= 0){
dp[i] = max(dp[i] , dp[i - v[j].cost] + v[j].prof);
}
}
}
fout<<dp[G];
}