PROBLEM LINK:
Author: Deepak Chaudhary
Tester: Lalit Singh
Editorialist: Deepak Chaudhary
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
You are given N number of different items of W1,W2 ... Wn weights and have profit of P1, P2 ... Pn respectively. You have to maximize the profit by picking the items. Maximum capacity C to pick items is also given.
QUICK EXPLANATION:
It is a Standard Fractional Knapsack Problem.
EXPLANATION:
You have to pick the items whose profit / weight is high bycare of capacity (i.e. the item which have minimum weight and maximum profit).
Common Mistake:
Print the final output after rounding-off the value.(i.e: 4.7 -> 5)
SOLUTIONS:
Setter's Solution
// Chef and Loss
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int test_cases;
cin >> test_cases;
while(test_cases--)
{
// Taking Input
int n, c;
cin >> n >> c;
int w[n],p[n];
for(int i = 0; i < n; i++)
cin >> w[i];
for(int i = 0; i < n; i++)
cin >> p[i];
// Main logic
multimap<double,int> mp;
for(int i = 0; i < n; i++)
{
mp.insert(make_pair((double)p[i]/w[i], i));
}
double result = 0;
multimap<double,int>::reverse_iterator rev;
for(rev = mp.rbegin(); rev != mp.rend(); rev++)
{
double fraction = (double)c/w[rev->second];
if(c >= 0 and w[rev->second] <= c)
{
result += p[rev->second];
c -= w[rev->second];
}
else if(c < w[rev->second])
{
result += fraction * p[rev->second];
break;
}
}
//Printing Final Output
cout<<(int)round(result)<<"\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
Tester's Solution
# Chef and Loss
# Knapsack Problem
class ItemValue:
"""Item Value DataClass"""
def __init__(self, wt, val, ind):
self.wt = wt
self.val = val
self.ind = ind
self.cost = val // wt
def __lt__(self, other):
return self.cost < other.cost
# Greedy Approach
class FractionalKnapSack:
@staticmethod
def getMaxValue(wt, val, capacity):
"""function to get maximum value """
iVal = []
for i in range(len(wt)):
iVal.append(ItemValue(wt[i], val[i], i))
# sorting items by value
iVal.sort(reverse=True)
totalValue = 0
for i in iVal:
curWt = int(i.wt)
curVal = int(i.val)
if capacity - curWt >= 0:
capacity -= curWt
totalValue += curVal
else:
fraction = capacity / curWt
totalValue += curVal * fraction
capacity = int(capacity - (curWt * fraction))
break
return totalValue
for _ in range(int(input())):
n, c = map(int, input().split())
w = list(map(int, input().split()))
p = list(map(int, input().split()))
print(round(FractionalKnapSack().getMaxValue(w, p, c)))
