Maximize the result for given array of values-CodePudding

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?

CodePudding user response：

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.