c++ - 修改后的 KnapSack 运行时错误

Question

我在解决 codechef 上的程序时遇到了一个问题，它是背包问题的修改版本.. 1.在这里我必须找到所有可能重量的最大成本..1<=n<=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;
    }

Answer 1

好吧，我不保证这会给你一个 AC

您在编写解决方案时忽略了约束

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 = sum = weight[i] * n 可以高达2*100000

相当于分配 K[100000][200000] 会产生运行时错误