Maximize the result for given array of values

I have an array of values example:

[[1,15], [3,20], [4,30]] each element holds two values, the amount we need to pay at 0th index and items we can collect at 1st index. Also, I have a budget of 4.

For this example, I can collect the elements [[1,15], [3,20]] because 1+3 = 4 which matches my budget, and the items I can collect are 15+20 = 35 which is the maximum.

I want to find the maximum number of items I can collect using this budget.

Here is my program:

public static long solve(List<List<Long>> arr, long budget) {
    arr.sort((a, b) -> {
        int z = Long.compare(a.get(0) , b.get(0));
        if(z == 0) {
            z = Long.compare(b.get(1) , a.get(1));
        }
        return z;
    });
    
    long total = 0;
    long result = 0;
    for(List<Long> list : arr) {
        if(total + list.get(0) <= budget) {
            total += list.get(0);
            result += list.get(1);
        } else {
            break;
        }
    }
}

This program works for the above problem.

This is another example in which the program gives the wrong result.

[[50, 200], [100, 800],[200, 1000], [500, 2000], [1000, 3000]], each element holds two values, the amount we need to pay at 0th index and items we can collect at 1st index. Also, I have a budget of 1700.

The result should be for items [200, 1000], [500, 2000], [1000, 3000] , so 1000+2000+3000 = 6000 but my program returns 4000 as because of my wrong approach.

What is the correct approach for this problem?

>Solution :

This is just a variant of the 0/1 knapsack problem.

• The cost of each item is the "weight"
• The budget becomes the "total weight"
• The number of items you can collect becomes the "value" for that item

Edit

If the total weight is large and the traditional dynamic programming approach can’t be used, you can redefine the states to get a solution, as demonstrated here.