Danial · 2015-06-25 20:07:12

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 · 2015-06-27 07:47:53

What data type did you use?

Can you post your code?

Danial · 2015-06-27 08:12:53

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 · 2015-06-29 02:58:44

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.