Knapsack with min weight

This variation of the knapsack problem requires a minimum weight. The goal is to minimize the cost while achieving at least the minimum weight.

For example, we have 6 items with weights {1, 1, 1, 5, 13, 3} and costs {1, 1, 1, 5, 10, 12}. Assume a minimum weight of 15.

The optimal solution is items {1, 2, 5} for a total weight of 15 and cost 12.

How should I go about implementing this algorithm as efficiently as possible? Greedy choices don't work, so should I modify the original dynamic programming solution to fit this problem? If so, how?

If it matters, I'm planning to write this in Java.

Let minCost[i] denote the minimum value that a knapsack with capacity i can hold, costs[i] represent the cost of the ith item, and weights[i] represent the weight of the ith item. Then, for each i, minVal[i] is the minimum of minVal[i - weights[j]] + costs[j] for all j from 1 to the number of items.

Then, the answer is the minimum value in the minCost array in the range from the minimum weight to the maximum weight.

final int[] weights = { 1, 1, 1, 5, 13, 3 }, costs = { 1, 1, 1, 5, 10, 12 };
final int minWeight = 15;
int maxWeight = 0;
for (final int weight : weights) {
    maxWeight += weight;
}
final int[] minCost = new int[maxWeight + 1];
for (int i = 1; i <= maxWeight; i++) {
    minCost[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < weights.length; i++) {
    for (int j = maxWeight; j >= weights[i]; j--) {
        if (minCost[j - weights[i]] != Integer.MAX_VALUE) {
            minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
        }
    }
}
int answer = Integer.MAX_VALUE;
for (int i = minWeight; i <= maxWeight; i++) {
    answer = Math.min(answer, minCost[i]);
}
System.out.println(answer);

Demo

This can be optimized by combining all weights greater than or equal to the minimum weight into a single state. This reduces the time and memory complexity to only depend on the minimum weight given by the problem.

final int[] weights = { 1, 1, 1, 5, 13, 3 }, costs = { 1, 1, 1, 5, 10, 12 };
final int minWeight = 15;
final int[] minCost = new int[minWeight + 1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[0] = 0;
for (int i = 0; i < weights.length; i++)
    for (int w = minWeight, adjustedWeight = Math.min(weights[i], minWeight); 
                w >= adjustedWeight; w--)
        if (minCost[w - adjustedWeight] != Integer.MAX_VALUE)
            minCost[w] = Math.min(minCost[w], 
                  minCost[w - adjustedWeight] + costs[i]);
System.out.println(minCost[minWeight]);