Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problema rucsacului 1/0 (nu pot fi luate bucati dintr-un obiect)
- // Rezolvare prin programare dinamica
- // date.in
- // 5 10
- //
- // 3 6
- // 2 3
- // 5 20
- // 1 7
- // 7 23
- #include "stdafx.h"
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- using namespace std;
- void date_in();
- void date_out();
- int n, c, sol[50][50];
- struct ob
- {
- int g, v;
- }X[20];
- int main()
- {
- int i, j;
- date_in();
- for(i = 1; i <= n; i++)
- for(j = 1; j <= c; j++)
- {
- if(X[i].g > j)
- sol[i][j] = sol[i-1][j];
- else if(X[i].g == j)
- {
- if(sol[i-1][j] < X[i].v)
- sol[i][j] = X[i].v;
- else
- sol[i][j] = sol[i-1][j];
- }
- else
- {
- if(sol[i-1][j-X[i].g])
- {
- if(sol[i-1][j-X[i].g] + X[i].v > sol[i-1][j])
- sol[i][j] = sol[i-1][j-X[i].g] + X[i].v;
- else
- sol[i][j] = sol[i-1][j];
- }
- else
- sol[i][j] = sol[i-1][j];
- }
- }
- date_out();
- return 0;
- }
- void date_in()
- {
- ifstream in("date.in");
- in >> n >> c;
- for(int i = 0; i < n; i++)
- in >> X[i].g >> X[i].v;
- }
- void date_out()
- {
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= c; j++)
- cout << setw(3) << sol[i][j];
- cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement