Question

Haloo , i have java program ,

Java Program , dynamic program

Given a knapsack with capacity B∈N and -n- objects with profits p0, ..., p n-1 and weights w0, ..., wn-1. It is also necessary to find a subset I ⊆ {0, ..., n-1} such that the profit of the selected objects is maximized without exceeding the capacity. However, we have another limitation: the number of objects must not exceed a given k ∈ N
Example: For the items in the following table, B = 10 and k = 3 ,4 is the maximum possible profit (without restriction of the items we could have achieved a profit of 6).
objects - Profit - weights
0 - 1 - 3
1 - 2 - 2
2 - 1 - 2
3 - 1 - 2
4 - 1 - 1
5 - 1 - 2
Create in the package ads.set1.knapsack a class MaxItemsKnapsackSolver. Implement the algorithm in the following method:
/**
* Solves the limited-items knapsack problem using a dynamic programming
* algorithm based on the one introduced in the lecture.
*
* @param items (possibly empty) list of items. All items have a profit
* {@code > 0.}
* @param capacity the maximum weight allowed for the knapsack ({@code >= 0}).
* @param maxItems the maximum number of items that may be packed
* ({@code >= 0}).
* @return the maximum profit achievable by packing at most {@code maxItems}
* with at most {@code capacity} weight.
*/
public static int pack(Item[] items, int capacity, int maxItems) {
// Implement me
return -1;
}
The available entries are described by instances of the Item class, which you can download here.

https://drive.google.com/file/d/15IAoYJQWc7kImRlYFOsEHP6oKER0QO2-/view?usp=sharing

Your tax should only consist of the class MaxItemsKnapsackSolver.

Answer 1

Solution for this problem is to consider all subsets of objects and calculate the total weight and profits of all subsets. Include only subsets whose total weight is smaller than maxWeight. From all such subsets, get the maximum value subset and return the same.

Code:

public class MaxItemsKnapsackSolver
{
   public static void main(String[] args) {
   int profit[] = new int[]{1, 2, 1,1,1,1};
int weight[] = new int[]{3, 2, 2,2,1,2};
int maxWeight = 10;
int lenProfit = 3;
System.out.println(pack(maxWeight, weight, profit, lenProfit));
   }
   //function to return max of two numbers
   static int maxNumber(int x, int y) { return (x > y)? x : y; }

// Returns the maximum value that can be put in a knapsack of capacity maxWeight
public static int pack(int maxWeight, int weight[], int profit[], int lenProfit)
{
int i, w;
int knapsack[][] = new int[lenProfit+1][maxWeight+1];

// Build table Knapsack[][] in bottom up manner
for (i = 0; i <= lenProfit; i++)
{
for (w = 0; w <= maxWeight; w++)
{
if (i==0 || w==0)
knapsack[i][w] = 0;
else if (weight[i-1] <= w)
knapsack[i][w] = maxNumber(profit[i-1] + knapsack[i-1][w-weight[i-1]], knapsack[i-1][w]);
else
knapsack[i][w] = knapsack[i-1][w];
}
}

return knapsack[lenProfit][maxWeight];
}
}