Description
Q1. Write a program in Java and return the time complexity of the following problem:
You are given N items, each has two parameters: a weight and a cost. Let’s define M as the sum of the weights of all the items.Your task is to determine the most expensive cost of a knapsack, which capacity equals to 1, 2, …, M. A cost of a knapsack equals to the sum of the costs of all the elements of the knapsack. Also, when you have a knapsack with a capacity is equal to C, then you can fill it with items, whose sum of weights is not greater than C.
Input: The first line of the input contains one integer N, denoting the number of the items. The next N lines contain two integers W and C each, denoting the weight and the cost of the corresponding item.
Output: For each capacity C (1 ≤ C ≤ M) of the knapsack, output a single integer – the most expensive cost for that capacity.
Constraints 3 ≤ N ≤ 100; 1 ≤ W ≤ 2, for each item; 1 ≤ C ≤ 109, for each item. Example
Bennett University Greater Noida Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35 Lab Code: ECSE202L Max Marks: 10
Input:
5
1 1
2 2
2 3
2 4
2 5
Output:
1 5 6 9 10 12 13 14 15
Explanations:
In the test case, M equals to 9.
For C = 1, it’s optimal to choose {1} items;
For C = 2, it’s optimal to choose {5} items;
For C = 3, it’s optimal to choose {1, 5} items;
For C = 4, it’s optimal to choose {4, 5} items;
For C = 5, it’s optimal to choose {1, 4, 5} items;
For C = 6, it’s optimal to choose {3, 4, 5} items;
For C = 7, it’s optimal to choose {1, 3, 4, 5} items;
For C = 8, it’s optimal to choose {2, 3, 4, 5} items;
For C = 9, it’s optimal to choose {1, 2, 3, 4, 5} items.
Q2. Write a program in Java and return the time complexity of the following problem.You are given N items, each has two parameters: a weight and a cost. Let’s define M as the sum of the weights of all the items.Your task is to determine the most expensive cost of a knapsack .Items can be broken into smaller pieces, hence thief can select fractions of items.
Input:
Items as (value, weight) pair
Bennett University Greater Noida Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35 Lab Code: ECSE202L Max Marks: 10 arr[] = {{60, 10}, {100, 20}, {120, 30}}
Knapsack Capacity, W = 50;
Output :
Maximum possible value = 240
By taking full items of 10 kg, 20 kg and
2/3rd of last item of 30 kg
