измененная ошибка времени выполнения KnapSack

Я сталкиваюсь с проблемой при решении программы на codechef, которая является модифицированной версией задачи о ранце.
1. здесь я должен найти максимальную стоимость для всего возможного веса.<= п<= W
2.Я решил это с помощью стандартного алгоритма DP … но каждый раз, когда я отправляю свой код .. я получаю ошибку во время выполнения …
Пожалуйста, посмотрите на мой код ..

   #include<bits/stdc++.h>
using namespace std;
#define  ll long long
ll _max(ll a,ll b){return a>b?a:b;}
ll sol[200009];
void knapsack(ll W,ll val[],ll wt[],ll n,ll sol[])
{
ll i,w;
ll K[n+1][W+1];for(ll i=0;i<=n;i++)
{
for(ll w=0;w<=W;w++)
{
if(i==0 || w==0)
K[i][w]=0;
else
{
if(wt[i-1]<=w)
K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
else
K[i][w]=K[i-1][w];
}
}
}
for(int j=0;j<W;j++)
{
sol[j]=K[n][j+1];
printf("%lld ",sol[j]);
}

}

int main()
{
ll n;
scanf("%lld",&n);
ll val[n];
ll wt[n];

ll sum =0;
for(ll i=0;i<n;i++)
{
scanf("%lld",&wt[i]);
scanf("%lld",&val[i]);
sum+=wt[i];
}

knapsack(sum, val, wt, n,sol);
return 0;
}

1

Решение

Хорошо, я не гарантирую, что это даст вам кондиционер

Вы пропустили ограничения при кодировании вашего решения

3 ≤ N ≤ 100000;

1 ≤ W ≤ 2, for each item;

1 ≤ C ≤ 109, for each item.

Ваша матрица

long long  K[n+1][W+1];

не будет выделено, потому что наибольшее значение n равно 100000 и

W = сумма = вес [i] * n, который может достигать 2 * 100000

что эквивалентно выделению K [100000] [200000], что даст ошибку времени выполнения

0

Другие решения


По вопросам рекламы [email protected]