## 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