Jul 2020
1 / 13
Jul 2020
Jul 2020
hemaruba
Jul '20

I’m getting WA :frowning:

#include
#include
#include
using namespace std;

int max(int a, int b)
{
return (a > b) ? a : b;
}

void knapsack(int W,vector<pair<int,int>> v,int n) //weight,profit
{
int k[101][501];

for (int i = 0; i <=n; i++)
{
	for (int w = 0; w <= W; w++)
	{
		if (i == 0 || w == 0)
			k[i][w] = 0;
		else if (w >= v[i-1].first)
		{
			k[i][w] = max(k[i - 1][w], v[i-1].second + k[i - 1][w - v[i-1].first]);
		}
		else
			k[i][w] = k[i - 1][w];
		
	}
}


int i = n, bal=k[n][W],w=W,sum=0;


	
	while (bal > 0 && i >= 0)
	{
		if (k[i][w] == k[i - 1][w])
			i--;
		else
		{
			
			sum += v[i-1].first;
			bal = bal - v[i - 1].second;
			w = w - v[i - 1].first;
			i--;
		}
	
	}
cout << sum << " " << k[n][W] << endl;

}
int main()
{
int W, n;

cin >> W >> n;

while (n!=0 || W!=0)
{
	
	vector<pair<int, int>> v;       //v[weight,int]

	for (int i = 0; i < n; i++)
	{
		int w, p;
		
		cin >> w >> p;
		v.push_back(make_pair(w, p));

	}
	sort(v.begin(), v.end());
	
	knapsack(W, v, n);

	cin >> W >> n;

}

}

  • created

    Jul '20

  • last reply

    Jul '20
  • 12

    replies

  • 780

    views

  • 2

    users

  • 6

    likes

  • 3

    links

simes
Jul '20

You’re getting the correct fun values, but sometimes, you pay too much for it.

hemaruba
Jul '20

Thankyou for the testcase :slight_smile:
But still I’m getting WA

#include
#include
#include
using namespace std;

bool sort2(const pair<int, int>& a, pair<int, int>& b)
{
if (a.first > b.first)
return true;
else if (a.first == b.first)
{
return (a.second < b.second);
}
else
return false;
}
int max(int a, int b)
{
return (a > b) ? a : b;
}
void knapsack(int W,vector<pair<int,int>> v,int n) //weight,profit
{
int k[101][501];

for (int i = 0; i <=n; i++)
{
	for (int w = 0; w <= W; w++)
	{
		if (i == 0 || w == 0)
			k[i][w] = 0;
		else if (w >= v[i-1].first)
		{
			k[i][w] = max(k[i - 1][w], v[i-1].second + k[i - 1][w - v[i-1].first]);
		}
		else
			k[i][w] = k[i - 1][w];
		
	}
}


int i = n, bal=k[n][W],w=W,sum=0;


	
	while (bal > 0 && i >= 0)
	{
		if (bal == k[i - 1][w])
		{
			if (k[i][v[i-1].first] == bal && k[i][v[i-1].first-1]!=bal)
			{
				//do nothing
			}
			else
			{
				i--;
				continue;
			}
		}
			
	
	
			
		sum += v[i-1].first;
		bal = bal - v[i - 1].second;
		w = w - v[i - 1].first;
		i--;
		
	
	}
cout << sum << " " << k[n][W] << endl;

}
int main()
{
int W, n;

cin >> W >> n;

while (n!=0 || W!=0)
{
	
	vector<pair<int, int>> v;       //v[weight,int]

	for (int i = 0; i < n; i++)
	{
		int w, p;
		
		cin >> w >> p;
		v.push_back(make_pair(w, p));

	}
	sort(v.begin(), v.end(),sort2);
	
	knapsack(W, v, n);

	cin >> W >> n;

}

}

simes
Jul '20

500 100
14 1
9 2
6 9
13 10
8 6
19 6
19 2
13 2
7 8
13 5
20 10
13 1
17 3
8 6
14 8
12 3
10 6
19 7
13 7
15 7
10 2
11 10
5 2
21 0
9 8
11 0
8 3
5 8
19 2
17 9
18 0
18 10
24 2
15 7
22 3
12 4
23 8
17 5
25 1
22 9
16 0
13 10
15 8
12 5
17 7
14 1
21 6
22 9
11 9
21 2
8 5
10 2
21 6
18 2
18 9
14 1
14 6
20 7
7 10
20 2
10 5
25 10
23 0
15 10
18 1
17 4
19 6
13 9
21 10
19 4
8 9
9 9
23 10
16 10
22 5
17 5
9 4
22 4
23 3
25 10
6 7
10 6
12 5
16 10
12 10
18 10
21 0
25 9
8 1
13 2
15 4
20 6
12 10
12 7
10 4
22 1
8 3
22 6
23 5
7 9
0 0

Expected answer

500 334

simes
Jul '20

So you do, my mistake. I must have confused myself. Then I don’t have a test case for you.

hemaruba
Jul '20

But I’m getting WA , i couldn’t find what mistake i made

simes
Jul '20
1

I know, frustrating isn’t it?

Best I can offer is for you to create some test cases. Post them here with your output, and I’ll push them through my solution and compare the results.