Pagini recente » Cod sursa (job #1593865) | Cod sursa (job #1922424) | Cod sursa (job #3142831) | Cod sursa (job #2724472) | Cod sursa (job #2670794)
#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 << ' ';
}*/
}
}