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