pages:
  • 1
Danial SAYS

The Complexity of my code due to this sentese in the question "It is guaranteed that in each test either
"B ≤ 50000 or max1 ≤ i ≤ n vi ≤ 500." is (B <= 50000)?O(nW):O(nV) so time limit is none sence is there any body here who can explain the time limit ???

AMiR SAYS

What data type did you use?

Can you post your code?

Danial SAYS

This is my code and I didn't see anything that may cause time limit mabay you can see it :)

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstdio>
using namespace std;
#define INF 999999999
long long val[101];
long long wt[101];
long long knapSack(long long W, long long n)
{
   long long i, w;
   long long K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i] <= w)
                 K[i][w] = max(val[i] + K[i-1][w-wt[i]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
   return K[n][W];
}
long long knapSack_Value(long long V,long long W, long long n)
{
   long long K[n+1][V+1],res = -1,res2;
   for (int i = 0; i <= n; i++)
   {
       for (int v = 0; v <= V; v++)
       {
           if (v > 0 && i == 0)
               K[i][v] = INF;
           else if(v ==0)
               K[i][v] = 0;
           else if(v < val[i])K[i][v] = K[i-1][v];
           else K[i][v] = min(wt[i] + K[i-1][v-val[i]], K[i-1][v]);
           if(i == n && K[n][v] <= W && res < K[n][v]){
               res = K[n][v];
               res2 = v;
           }
       }
   }
   return res2;
}
int main()
{
    long long n,W;
    while(true){
        cin>>n>>W;
        if(n == 0 && W == 0)return 0;
        int V = 0;
        for(int i=1 ; i<=n ; i++){
            cin>>val[i];
            V+=val[i];
        }
        for(int i=1 ; i<=n ; i++){
            cin>>wt[i];
        }
        if(W <= 50000){
            cout<<knapSack(W, n)<<endl;
        }
        else{
            cout<<knapSack_Value(V,W,n)<<endl;
        }
   }
}
AMiR SAYS

Can you replace long long with int?

I'm note sure using int will cause any problems, I used int and I got accepted.

Operations take much longer on long long.