What's wrong with this code?

[kimchiboy03]

Hello , I am currently trying to solve this knapsack problem:

You are a burglar, with nothing in your hand but a knapsack. You are about to break into the house that all burglars dream of entering, when you remember the scrap piece of paper in a pocket of your jacket. This piece of paper tells you everything you need to know about every type of item inside the house—the size and the value.

You think back: burglars from previous generations have repeatedly said that there are an infinite number of items of any item type. As soon as a particular item type caught their eye, they would stuff as many of those items as they could into a knapsack. But not you. You want to extract the maximum value out of this idolised house, but you don't know how.

So you go home. You rest your very light knapsack next to your laptop and write a program telling you what to steal.

Input
The first line contains integers N and M, representing the number of item types and the size of the knapsack. Following this will be N lines, one for each item type, each of the form s v, representing the size and value of each type of item respectively. Of these N lines, the ith line corresponds to the ith item type. Note that items types are not guaranteed to appear in any particular order.

You may assume that N,M≤1000, and that s,v≤1000 for each item type.

Output
Your program should output a list of item types, showing you which items to steal. This list should be in ascending order, with one item type on each line, assuming item types are numbered from 1 to N.

If there is more than one possible solution, any correct solution will suffice.

Sample Input
The following corresponds to the example provided by Sedgewick on page 597, with a knapsack of size 17. The optimal filling uses one item of type 1 and two of type 3, giving a total value of 24.

Sample Input 1
5 17
3 4
4 5
7 10
8 11
9 13
Sample Output 1
1
3
3

Sample Input 2
3 10
5 4
5 4
6 6
Sample Output 2
1
2

Although my code seems to successfully output the sample outputs, while running it through the online test cases, it seems to never end. Can someone please tell me what is wrong with my code please?

Thanks in advance.

My Code:

#include <iostream>
#include <vector> 

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int numItems, maxW;
	cin >> numItems >> maxW;
	
	vector<vector<int> > dp(numItems, vector<int>(maxW + 1, 0));
	vector<vector<vector<int> > > ty(numItems, vector<vector<int> >(maxW + 1));
	
	int size, value;
	cin >> size >> value;
	for(int i = size; i < maxW + 1; i++)
	{
		dp[0][i] = value;
		ty[0][i].push_back(1);
	}
	
	for(int i = 1; i < numItems; i++)
	{
		cin >> size >> value;
		for(int j = 0; j < maxW + 1; j++)
		{
			if(size > j)
			{
				dp[i][j] = dp[i - 1][j];
				ty[i][j].insert(ty[i][j].end(), ty[i - 1][j].begin(), ty[i - 1][j].end());
			}
			else
			{
				int a = dp[i - 1][j];
				int b = dp[i - 1][j - size] + value;
				
				dp[i][j] = (a > b ? a : b);
				if(a > b)
				{
					ty[i][j].insert(ty[i][j].end(), ty[i - 1][j].begin(), ty[i - 1][j].end());
				}
				else
				{
					ty[i][j].insert(ty[i][j].end(), ty[i - 1][j - size].begin(), ty[i - 1][j - size].end());
					ty[i][j].push_back(i + 1);
				}
			}
		}
	}
	
	for(int i = 0; i < ty[numItems - 1][maxW].size(); i++)
	{
		cout << ty[numItems - 1][maxW][i] << "\n";
	}
	
	return 0;
}

[kbw]

Can you explain (with words) what your algorithm is?

There's are number of inconsistencies with your example and code, I don't want to debug those. It's much more productive if you describe your algorithm, fix that it needs attention, then see how it's implemented.

[kimchiboy03]

@kbw

The ty vector should look something like this: https://pasteboard.co/HkkbYuJ.png

and the dp vector should look something like this: https://pasteboard.co/HkkcFfZ.png

Currently, I'm just using a typical bottom-up dynamic programming solution.

[kbw]

I can't make sense of what you've done, and without your algorithm, no chance.

It's not clear why you've broken the tie between cin/cout.

Your indexing in the first loop is wrong.

It's not obvious to me why your variables are called dp, ty.