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.