Я сталкиваюсь с проблемой при решении программы на 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;
}
Хорошо, я не гарантирую, что это даст вам кондиционер
Вы пропустили ограничения при кодировании вашего решения
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], что даст ошибку времени выполнения