Coursera's Algorithmic toolbox assignment solutions( Money Change, Maximum Value of the Loot ) :
Problem 1: Money Change
Solution: (in c++)
( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder)
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,count=0;
cin>>n;
while(n!=0)
{
if(n>=10)
{
n-=10;
count++;
}
else if(n<10 && n>=5)
{
n-=5;
count++;
}
else{
n-=1;
count++;
}
}
cout<<count;
}
This code is simple. There's no need for any explanation.
or
you can also use this code below if denominations are given as input in descending order.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; //n=no. of denominations
cin>>n;
int d[n],s,coins[n],count=0; //d[n] is array of denominations ,
for(int i=1;i<=n;i++) //s=amount for which change is needed
{
cin>>d[i]; //enter the denominations in descending order only
}
cin>>s;
for(int i=1;i<=n;i++)
{
coins[i]=floor(s/d[i]);
s=s%d[i];
if(coins[i]!=0)
{
count+=coins[i];
}
}
cout<<count;
}
Problem 2: Maximum Value of the Loot
Solution: (in c++)
( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder)
#include<bits/stdc++.h>
using namespace std;
struct items
{
double v,w,r; //v=value , w=weight , r=ratio of v/w
};
{
return(i1.r>i2.r);
}
int main()
{
int n,i;
double totalvalue = 0, totalweight = 0,wt,W;
cin>>n>>W;
struct items it[n];
for(i=0;i<n;i++)
{
cin>>it[i].v>>it[i].w;
it[i].r=it[i].v/it[i].w;
}
sort(it,it+n,compare); //arrays sorted accordingly
{
if(totalweight+it[i].w<= W) //see note below
{
totalvalue+=it[i].v ;
totalweight+=it[i].w;
}
else
{
wt=W-totalweight;
totalvalue+=(wt*it[i].r);
totalweight+=wt;
break;
}
}
cout.precision(10);
cout<<totalvalue;
}
Well , the solution is here. What i did here is in accordance with the lecture , we will first see which item has the highest v/w i.e r value and then we will put that item whole in the knapsack if possible , if space is left , we will take the next maximum v/w value and put that item whole in the knapsack if possible. We will repeat this procedure until the knapsack becomes full. This will help us find the optimal solution for our problem.
Guys , if you have any queries related to a question or need more explanation, comment down below!
Suppose if someone copies the code as it is, what are the chances to get caught in plagiarism? And what can be the consequences?
ReplyDeleteI have heard that coursera detects the same code that is submitted by another person. In that case they will end your course. So don't just copy paste. Try to understand the problem and use different variables.
Delete