How to create a completely responsive Online Company Website Design Template – Using HTML – CSS – JavaScript. Online Company Website Design Free Download
And the base case will be, if make can be made after trying all the coins then return 1, otherwise return 0. Complete code:
int coin[]={5,8,11,15,18}; //value of coins available
int make; //our target value
int dp[6][100];
int call(int i,int amount)
{
if(i>=5) { //All coins have been taken
if(amount==make) return 1;
else return 0;
}
if(dp[i][amount]!=-1) return dp[i][amount]; //no need to calculate same state twice
int ret1=0,ret2=0;
if(amount+coin[i]<=make) ret1=call(i,amount+coin[i]); //try to take coin i
ret2=call(i+1,amount); //dont take coin i
return dp[i][amount]=ret1|ret2; //storing and returning.
}
int main()
{
// freopen(“in”,”r”,stdin);
while(cin>>make)
{
memset(dp,-1,sizeof(dp));
cout<<call(0,0)<<endl;
}
return 0;
}
Now what if you were told how many times a value should be generated? For example, 18 can be made in 2 ways, in this case, instead of returning ret1|ret2, return ret1 + ret2, then all the ways that can be made are added. This is what the uva-674 problem says to do, fix it immediately.
Now look at an interesting optimization. We have re-initialized or cleared the dp array after every makes input. If it didn’t have to do that, it would take much less time, because the same value wouldn’t have to be calculated over and over again. But having to clear because the function depends on an external global variable, “if(amount==make)return 1;” This line is causing trouble, make
Its value is different for each case, so all calculations have to be done anew each time. If we put make as a state it works but the state becomes huge. From this we reverse the problem. Suppose you have 20 bucks in the beginning, you have to make zero bucks by donating coins of different amounts. The code will now look like this:
Online Company Website Design Free Download
int coin[]={5,8,11,15,18}; //value of coins available
int make=18; //we will try to make 18
int dp[6][100];
int call(int i,int amount)
{
if(i>=5) { //All coins have been taken
if(amount==0) return 1;
else return 0;
}
if(dp[i][amount]!=-1) return dp[i][amount]; //no need to calculate same state twice
int ret1=0,ret2=0;
if(amount-coin[i]>=0) ret1=call(i,amount-coin[i]); //try to take coin i
ret2=call(i+1,amount); //dont take coin i
return dp[i][amount]=ret1|ret2; //storing and returning.
}
int main()
{
// freopen(“in”,”r”,stdin);
memset(dp,-1,sizeof(dp));
while(cin>>make)
{
cout<<call(0,make)<<endl;
}
return 0;
}
Notice that I did the same thing as before, except instead of adding I tried to make null from make. The advantage is that now the function does not depend on any mutable global variables, so there is no need to clear the DP array in the main function loop. This trick works because the coin stays the same every time, it doesn’t work if the value of the coin changes. DP’s problem is sometimes giving too many test cases so that the time limit is not passed if cleared repeatedly.
Complexity
The size of the dp array will be the number of coins × the maximum value to be generated. Then the memory complexity is O(numberofcoin×make).
Each cell of the DP array may need to be filled, so the time complexity is also O(numberofcoin×make) here.
. If there were any extra loops running inside, that would also add to the time complexity.
1231 – Coin Change (I) problem in LightOZ asks to find out how many coins can create a value, but the maximum number of times each coin can be used, i number coin Ci
Bars can be used. You can handle this condition in two ways. 3rd you can have a state taken which will tell how many times you have taken i number, when Ci number is used move to the next coin.
int call(int i, int taken_i, int amount)
2nd way is Ci inside the function
Try to make the amount by taking the coin as many times as possible by running a loop until, in this case less memory will be required. So today’s 2nd task is to solve this problem.
Another name of coin change problem is subset sum problem, because we have to take a subset from a set of numbers whose sum is equal to a certain value.
The rock-climbing problem
You are given a 2D grid:
-1 2 5
4 -2 3
1 2 10
You are at the beginning in cell (0,0). You can only go in 3 directions:
(i + 1, j)
(i + 1,j – 1)
(i + 1, j + 1)
When you go to each cell, the number of that cell is added to your points. How many points can you make the maximum? This problem is also called rock climbing problem.
The highest point in the above grid is 7 = -1+-2+10. For this problem:
State: Which cell are you in now?
How to move from one state to another: Try to move from each cell to 3 directions, returning the one that gets the highest points.
Basecase: If you go outside the grid, nothing else can be taken, return null.
#define inf 1 << 28
int mat[][10] = {
{ -1, 2, 5 },
{ 4, -2, 3 },
{
1, 2, 10,
}
};
int dp[10][10];
int r = 3, c = 3;
int call(int i, int j)
{
if (i >= 0 && i < r and j >= 0 and j < c) //if still inside the array
{
if (dp[i][j] != -1)
return dp[i][j];
int ret = -inf;
//try to move to 3 direction, also add current cell’s point
ret = max(ret, call(i + 1, j) + mat[i][j]);
ret = max(ret, call(i + 1, j – 1) + mat[i][j]);
ret = max(ret, call(i + 1, j + 1) + mat[i][j]);
return dp[i][j] = ret;
}
else
return 0; //if outside the array
}
int main()
{
// READ(“in”);
mem(dp, -1);
printf(“%d\n”, call(0, 0));
return 0;
}
Why is the condition to move in 3 directions? Where would the problem be if you move to adjacent 4 cells? Then a cycle would have been created, before a function had completed its work and the function would have been called again in recursion, this solution would not have worked. Here we are moving in 3 directions, no cycle is created, i.e. we cannot start from any state and return to that state again. If the cycle were created then the recursive function would run forever. So while writing the DP solution one must take care whether the cycle is being generated or not.
Online Company Website Design Free Download
1004 – Monkey Banana Problem This problem is very similar to the above problem, there will be no problem to solve it. If you can bfs/dfs then solve uva-11331 problem, (hint:bicoloring+knapsack). Also try these:
Uva 11137: Ingenuous Cubrency(Coin change)
Codeforces 118D: Caesar’s Legions (4 states)
Light oj 1047: Neighbor House
Timus 1017: Staircases
Try to solve all the problems, if you get stuck, no problem, keep thinking, also solve as many problems as you can related to knapsack and coin change, as you will reduce the details in the basic parts and discuss more about new problems and techniques.
Happy Coding!
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.