jjzjj

c++ - 为什么贪婪的方法在这种情况下不起作用？

coder 2024-02-05 原文

我正在尝试解决以下问题 SPOJ problem .

输入是: 1.总重量一定的钱币， 2. 使用币种的币值及对应权重。

目标是找到给定金额的最小可能货币值(value)。

我的方法是将货币的硬币按各自的值(value)/重量比升序排序，然后贪婪地在总和中尽可能多地拟合第一个硬币的重量(跟踪有多少次)，然后将第二枚硬币的重量尽可能多地放入余数中，以此类推，对于所有硬币或直到余数为零(如果不是，则这种情况是不可能的)。

法官说我的回答是错误的。你能给我一个关于算法错误的提示吗？

我的代码在这里:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int weight_t;
typedef unsigned int value_t;

struct coin {
    weight_t weight;
    value_t value;
    double value_per_gram;
};

coin make_coin(weight_t weight, value_t value) {
    coin ret;
    ret.weight = weight;
    ret.value = value;
    ret.value_per_gram = (double)(value/weight);
    return ret;
}

bool compare_by_value_per_gram(const coin& coin1, const coin& coin2) {
    return coin1.value_per_gram < coin2.value_per_gram;
}

int main() {
    unsigned int test_cases;
    cin >> test_cases;
    while(test_cases--) {
        unsigned int number_of_coins = 0;
        weight_t empty_pig, full_pig, coins_weight, coin_weight, min_value = 0;
        value_t coin_value = 0;
        vector<coin> coins;
        vector<unsigned int> how_many_coins;
        cin >> empty_pig >> full_pig;
        coins_weight = full_pig - empty_pig;
        cin >> number_of_coins;

        while(number_of_coins--) {
            cin >> coin_value >> coin_weight;
            coins.push_back(make_coin(coin_weight, coin_value));
        }
        sort(coins.begin(), coins.end(), compare_by_value_per_gram);

        how_many_coins.resize(coins.size());
        for(unsigned int i = 0; i < coins.size() && coins_weight > 0; i++) {
            how_many_coins[i] = coins_weight/coins[i].weight;
            coins_weight %= coins[i].weight;
            min_value += coins[i].value * how_many_coins[i];
        }
        if(coins_weight == 0) cout << "The minimum amount of money in the piggy-bank is " << min_value << "." << endl;
        else cout << "This is impossible." << endl;
    }
    return 0;
}

最佳答案

一个简单的反例是两种类型的硬币(weight,value) = {(2,3), (3,3)}，带有小 pig 重量为 4。您将尝试放入重量为 3 的“更差”硬币，但无法匹配重量为 4 的硬币。但是对于 2*(2,3) 个硬币，这种情况很有可能发生，

这可以与 knapsack problem 非常相似地解决。 , 在 Dynamic Programming 上使用一些修改解决方案:

这个想法是模仿穷举搜索。在每一步中，您都会查看当前的候选代币，您有两个选择:接受它，或者前进到下一个代币。

f(x,i) = INFINITY          x < 0 //too much weight 
f(0,i) = 0                       //valid stop clause, filled the piggy completely.
f(x,0) = INFINITY          x > 0 //did not fill the piggy
f(x,i) = min{ f(x,i-1) , f(x-weight[i], i) + value[i] } //take minimal guaranteed value
               ^                  ^
        coin is not used      use this coin
            anymore

调用 f(Weight,#coins_in_currency)

当使用 DP(自下而上或自上而下)时，此解决方案的时间复杂度为 O(n*W)，其中 W 是所需的小 pig 重量n 是货币中硬币的数量。

关于c++ - 为什么贪婪的方法在这种情况下不起作用？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25493245/

amp43valueweightcoinsc++algorithmgreedy

有关c++ - 为什么贪婪的方法在这种情况下不起作用？的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  6. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  7. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  8. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  9. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  10. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

随机推荐