Cod sursa(job #2670794)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 10 noiembrie 2020 18:07:02
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

int n, g;
int castig[101], greutate[101];
int dp[301], v[301][101];

ifstream fin("rucsac.in	");
ofstream fout("rucsac.out");

int main()
{
    fin >> n >> g;
    for(int i = 1; i <= n; i ++)
        fin >> greutate[i];
    for(int i = 1; i <= n; i ++)
        fin >> castig[i];
    for(int i = 1; i <= g; i ++)
        dp[i] = -1;
    for(int i = 1; i <= g; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(greutate[j] <= i && dp[i-greutate[j]] != -1 && v[i-greutate[j]][j] == 0)
            {
                if(dp[i] < castig[j] + dp[i-greutate[j]])
                {
                    dp[i] = castig[j] + dp[i-greutate[j]];
                    for(int k = 1; k <= n; k ++)
                        v[i][k] = v[i-greutate[j]][k];
                    v[i][j] = 1;
                }
            }
        }
        ///7 100
        ///80 10 20 10 100 30 55
        ///8 20 5 1 10 30 20
    }
    if(dp[g] == -1)
        fout << "IMPOSIBIL" << '\n';
    else
    {
        fout << dp[g] << '\n';
        /*for(int k = 1; k <= n; k ++)
        {
            if(v[g][k])
                cout << k << ' ';
        }*/
    }
}