{"id":34070,"date":"2023-02-22T05:57:32","date_gmt":"2023-02-22T00:27:32","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/"},"modified":"2023-02-22T05:57:32","modified_gmt":"2023-02-22T00:27:32","slug":"solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/","title":{"rendered":"[Solved] An algorithm to find the exact amount to add to a top-up a card"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

The problem you describe is actually a very difficult problem in general, since it is related to the knapsack problem<\/a>. But it is only hard if you allow very large amounts of money on the card and very many different prices.<\/p>\n

For your real world problem with very few different prices you can solve this problem by complete enumeration: say you have one fixed to-up amount c and prices p_1$, …, p_n create nested loops of depth n, like this<\/p>\n

to_up = 0; \/\/ this will contain the number of 0.25 increases\nno_p1 = 0; \/\/ this will contain the times p1 needs to be spent\n...\nno_pn = 0;\nstarting_amount = 42.0; \/\/ specify your starting amount here\nWHILE (true) \/\/ to_up loop\n  WHILE (true) \/\/ number of p1\n     WHILE (true) \/\/ number of p2\n        \/\/ ... repeat with as many different prices you have\n        \/\/ now check for solution:\n        IF(starting_amount - to_up * 0.25 - no_p1 * p1 - ... - no_pn * pn == 0)\n        BEGIN    \n           print 'found solution: ups: %1, no p1: %2, ..., no pn: %n', no_p1, ..., no_pn\n           EXIT(0);\n        END\n        no_p2++;\n     END\n     no_p1++;\n  END\n  to_up++;\nEND\n<\/code><\/pre>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            <\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved An algorithm to find the exact amount to add to a top-up a card <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] The problem you describe is actually a very difficult problem in general, since it is related to the knapsack problem. But it is only hard if you allow very large amounts of money on the card and very many different prices. For your real world problem with very few different prices you can solve … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,324],"class_list":["post-34070","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-c"],"yoast_head":"\n[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The problem you describe is actually a very difficult problem in general, since it is related to the knapsack problem. But it is only hard if you allow very large amounts of money on the card and very many different prices. For your real world problem with very few different prices you can solve ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2023-02-22T00:27:32+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] An algorithm to find the exact amount to add to a top-up a card\",\"datePublished\":\"2023-02-22T00:27:32+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/\"},\"wordCount\":112,\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"keywords\":[\"algorithm\",\"c++\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/\",\"name\":\"[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\"},\"datePublished\":\"2023-02-22T00:27:32+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] An algorithm to find the exact amount to add to a top-up a card\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\\\/\\\/jassweb.com\"],\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/author\\\/jaspritsinghghumangmail-com\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb","og_description":"[ad_1] The problem you describe is actually a very difficult problem in general, since it is related to the knapsack problem. But it is only hard if you allow very large amounts of money on the card and very many different prices. For your real world problem with very few different prices you can solve ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/","og_site_name":"JassWeb","article_published_time":"2023-02-22T00:27:32+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] An algorithm to find the exact amount to add to a top-up a card","datePublished":"2023-02-22T00:27:32+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/"},"wordCount":112,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","c++"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/","url":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/","name":"[Solved] An algorithm to find the exact amount to add to a top-up a card - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2023-02-22T00:27:32+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-an-algorithm-to-find-the-exact-amount-to-add-to-a-top-up-a-card\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] An algorithm to find the exact amount to add to a top-up a card"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/34070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=34070"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/34070\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=34070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=34070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=34070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}