Saturday, April 6, 2013

Modify Coin Change To Keep Track Of Used Coins? - C And C++ ...


Example
#{example}
"); ipb.editor_values.get('templates')['togglesource'] = new Template("
??? Cancel Source Edit
"); ipb.editor_values.get('templates')['toolbar'] = new Template(""); ipb.editor_values.get('templates')['button'] = new Template("
  • Icon
  • "); ipb.editor_values.get('templates')['menu_item'] = new Template("
  • #{title}
  • "); ipb.editor_values.get('templates')['togglesource'] = new Template("
    ??? Cancel Source Edit
    "); ipb.editor_values.get('templates')['emoticons_showall'] = new Template(""); ipb.editor_values.get('templates')['emoticon_wrapper'] = new Template("

    Emoticons

    "); // Add smilies into the mix ipb.editor_values.set( 'show_emoticon_link', false ); ipb.editor_values.set( 'bbcodes', $H({"snapback":{"id":"1","title":"Post Snap Back","desc":"This tag displays a little linked image which links back to a post - used when quoting posts from the board. Opens in same window by default.","tag":"snapback","useoption":"0","example":"[snapback]100[/snapback]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"topic":{"id":"5","title":"Topic Link","desc":"This tag provides an easy way to link to a topic","tag":"topic","useoption":"1","example":"[topic=1]Click me![/topic]","switch_option":"0","menu_option_text":"Enter the topic ID","menu_content_text":"Enter the title for this link","single_tag":"0","optional_option":"0","image":""},"post":{"id":"6","title":"Post Link","desc":"This tag provides an easy way to link to a post.","tag":"post","useoption":"1","example":"[post=1]Click me![/post]","switch_option":"0","menu_option_text":"Enter the Post ID","menu_content_text":"Enter the title for this link","single_tag":"0","optional_option":"0","image":""},"spoiler":{"id":"7","title":"Spoiler","desc":"Spoiler tag","tag":"spoiler","useoption":"0","example":"[spoiler]Some hidden text[/spoiler]","switch_option":"0","menu_option_text":"","menu_content_text":"Enter the text to be masked","single_tag":"0","optional_option":"0","image":""},"acronym":{"id":"8","title":"Acronym","desc":"Allows you to make an acronym that will display a description when moused over","tag":"acronym","useoption":"1","example":"[acronym='Laugh Out Loud']lol[/acronym]","switch_option":"0","menu_option_text":"Enter the description for this acronym (EG: Laugh Out Loud)","menu_content_text":"Enter the acronym (EG: lol)","single_tag":"0","optional_option":"0","image":""},"hr":{"id":"12","title":"Horizontal Rule","desc":"Adds a horizontal rule to separate text","tag":"hr","useoption":"0","example":"[hr]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"1","optional_option":"0","image":""},"php":{"id":"14","title":"PHP Code","desc":"Allows you to enter PHP code into a formatted/highlighted syntax box","tag":"php","useoption":"0","example":"[php]$variable = true;\n\nprint_r($variable);[/php]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"html":{"id":"15","title":"HTML Code","desc":"Allows you to enter formatted/syntax-highlighted HTML code","tag":"html","useoption":"0","example":"[html]\n \n[/html]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"sql":{"id":"16","title":"SQL Code","desc":"Allows you to enter formatted/syntax-highlighted SQL code","tag":"sql","useoption":"0","example":"[sql]SELECT p.*, t.* FROM posts p LEFT JOIN topics t ON t.tid=p.topic_id WHERE t.tid=7[/sql]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"xml":{"id":"17","title":"XML Code","desc":"Allows you to enter formatted/syntax-highlighted XML code","tag":"xml","useoption":"0","example":"[xml]\n \n Test\n \n[/xml]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"member":{"id":"31","title":"Member","desc":"Given a member name, a link is automatically generated to the member's profile","tag":"member","useoption":"1","example":"[member=skyhawk133] runs this site.","switch_option":"0","menu_option_text":"Input Username of Member","menu_content_text":"","single_tag":"1","optional_option":"0","image":"memberbbcode.png"},"extract":{"id":"33","title":"Extract Blog Entry","desc":"This will allow users to define an extract for an entry. Only this piece of the entry will be displayed on the main blog page and will show up in the RSS feed.","tag":"extract","useoption":"0","example":"[extract]This is an example![/extract]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"blog":{"id":"34","title":"Blog Link","desc":"This tag provides an easy way to link to a blog.","tag":"blog","useoption":"1","example":"[blog=100]Click me![/blog]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"entry":{"id":"35","title":"Blog Entry Link","desc":"This tag provides an easy way to link to a blog entry.","tag":"entry","useoption":"1","example":"[entry=100]Click me![/entry]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"twitter":{"id":"36","title":"Twitter","desc":"A tag to link to a user's twitter account","tag":"twitter","useoption":"0","example":"[twitter]userName[/twitter]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":"twitter.png"},"inline":{"id":"37","title":"Inline Code","desc":"Formats code inline instead of in a seperate code box. ","tag":"inline","useoption":"0","example":"[inline]style=\"font-size: 12px;\"[/inline]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":""},"il":{"id":"38","title":"Abbreviated Inline (IL)","desc":"Abbreviated version of the [inline] tag. ","tag":"il","useoption":"0","example":"[il]Code Here[/il]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"0","image":"il2.png"},"code":{"id":"41","title":"Code","desc":"Allows you to enter general code","tag":"code","useoption":"1","example":"[code]$text = 'Some long code here';[/code]","switch_option":"0","menu_option_text":"","menu_content_text":"","single_tag":"0","optional_option":"1","image":""}}) ); ipb.vars['emoticon_url'] = "http://cdn.dreamincode.net/forums/public/style_emoticons/default"; //Search Setup ipb.vars['search_type'] = 'forum'; ipb.vars['search_type_id'] = 15; ipb.vars['search_type_2'] = 'topic'; ipb.vars['search_type_id_2'] = 317837; //]]>

    2 Replies - 0 Views - Last Post: 36 minutes ago Rate Topic: -----

    #1 IngeniousHax ?Icon User is online

    Reputation: 75

    • Posts: 1,329
    • Joined: 28-March 09

    Posted 59 minutes ago

    Alright, so I got the coin change problem working just fine, but I can't seem to keep track of the used coins. I get incorrect values since I went about it in a recursive manner, so when values are stored in the array, it's not the correct index.

    I get the following output from the entire program:

    Minimum number of coins needed to make change for $12.00: 2
    --[ The table for the minimum number of coins at each denomination ]--
    0 0
    1 1
    2 2
    3 3
    4 4
    5 5
    6 1
    7 2
    8 3
    9 4
    10 1
    11 2
    12 2
    0 : {0, 0, 0, 0, 0}
    1 : {1, 0, 0, 0, 0}
    2 : {10, 1, 6, 6, 1}
    3 : {1, 1, 1, 1, 10}
    4 : {6, 1, 10, 6, 1}
    5 : {6, 1, 6, 1, 6}
    6 : {1, 0, 0, 0, 0}
    7 : {0, 0, 0, 0, 0}
    8 : {0, 0, 0, 0, 0}
    9 : {0, 0, 0, 0, 0}
    10 : {0, 0, 0, 0, 0}
    11 : {0, 0, 0, 0, 0}
    12 : {0, 0, 0, 0, 0}

    And here is my code:

    
 #include <iostream> #include <iomanip> #include <string> using namespace std; #define INF 10000							// A large value that denotes infinity  /* Globals, Shouldn't be used, but makes my life easier for the mean time */ int denominations[3]; int change(int); void vals(); int c[13][5] = {{0}, {0}}; int v[13] = {0}; int j = 2, 	k = 0;   int main(int argc, char* argv[]) { 	int coin = 12; 	int i = 0;  	denominations[0] = 1; 	denominations[1] = 6; 	denominations[2] = 10;  	for(i = 0; i < 13; i++) 		v[i] = INF;   	v[0] = 0; 	c[1][0] = v[1] = 1; 	cout << "Minimum number of coins needed to make change for $12.00: " << change(coin) << endl; 	cout << "--[ The table for the minimum number of coins at each denomination ]--" << endl; 	 	for(i = 0; i < 13; i++) 		cout << i << "\t" << v[i] << endl;  	vals();  	cin.get(); } 
    
 int change(int init_val) { 	int test = INF, 		min = INF, 		remaining = 0, 		i = 0;  	if(init_val > 1) 	{ 		for(i = 2; i >= 0; i--) 		{ 			if(init_val >= denominations[i]) 			{ 				remaining =  init_val - denominations[i]; 				c[j][k] = denominations[i]; 				k++; 				if(v[remaining] != INF) 				{ 					test = 1 + v[remaining]; 				} 				else if(v[remaining] == INF) 				{ 					test = 1 + change(remaining); 				} 				if(test <= min) 				{ 					min = test; 				} 			} 		} 		v[init_val] = min; 		return v[init_val]; 	} 	if(init_val == 1) 	{ 		min = v[1]; 		test = 1; 		j++; 		return v[1]; 	} 	if(init_val == 0) 	{ 		min = v[0]; 		test = 0; 		k = 0; 		j++; 		return v[0]; 	} } 

    Any help or pushes in the correct direction would be greatly appreciated.

    This post has been edited by IngeniousHax: 53 minutes ago


    Is This A Good Question/Topic? 0

    Replies To: Modify coin change to keep track of used coins?

    #2 andrewsw ?Icon User is online

    Reputation: 762

    • Posts: 2,380
    • Joined: 12-December 12

    Re: Modify coin change to keep track of used coins?

    Posted 45 minutes ago

    What "coin change problem" ??


    #3 IngeniousHax ?Icon User is online

    Reputation: 75

    • Posts: 1,329
    • Joined: 28-March 09

    Re: Modify coin change to keep track of used coins?

    Posted 36 minutes ago

    It's a dynamic programming approach to making change for some value using the least amount of denominations possible, given that you have an infinite supply of each denomination.

    This post has been edited by IngeniousHax: 35 minutes ago


    Page 1 of 1


    Source: http://www.dreamincode.net/forums/topic/317837-modify-coin-change-to-keep-track-of-used-coins/

    lin j.r. smith espn jeremy lin sleigh bells meek sturgis sturgis

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.