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 ???
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
.
Login please!
In order to post something you must login first. You can use the form in the top of this page.