小编Deg*_*taf的帖子

我无法弄清楚动态硬币更改问题的最后一段代码.我已经包含了以下代码.

我无法弄清楚最后一个else.我应该在那时使用贪婪算法,还是可以从表中已有的值计算答案？我努力尝试理解这个问题,我觉得我非常接近.该方法通过创建表并使用存储在表中的结果来解决较大的问题而不使用递归,从而找到进行特定更改所需的最小硬币数量.

public static int minCoins(int[] denom, int targetAmount){
    int denomPosition; // Position in denom[] where the first spot
                       // is the largest coin and includes every coin
                       // smaller.
    int currentAmount; // The Amount of money that needs to be made
                       // remainingAmount <= initalAmount
    int[][] table = new int[denom.length][targetAmount+1];
    for(denomPosition = denom.length-1 ; denomPosition >= 0 ; denomPosition--) {
        for(currentAmount = 0 ; currentAmount <= targetAmount ; currentAmount++){
            if (denomPosition == denom.length-1){
                table[denomPosition][currentAmount] = 
                     currentAmount/denom[denomPosition];
            } …

在我的项目中,问题的一部分就在那里.但为了简化,这里的问题正在制定中.有两个正的共素整数:a和b,其中a < b.列出a从1到1的倍数,b-1然后是模数运算b.

a mod b,2*a mod b,3*a mod b,...,(b-1)*a mod b

现在,还有另一个整数n ( 1 <= n < b).通过n列表中的第一个数字,我们必须找到多少数字,比如说m(1 <= m < b).这可以用蛮力方法完成,从而给出一个 O(n).

一个例子:

a=6, b=13, n=8, m=6

清单是:

6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7

这是从1到12的数字的排列,因为如果我们包括另一个数,即任何两个共素的模运算产生数字的排列,即0.如果我们采取a= 2, b=13,那么列表将是2, 4, 6, 8, …

自昨天站在超市的销售点以来,再一次试图在试图忽略我身后不耐烦和紧张的队列的同时试图找到我的硬币的最佳分区时,我一直在思考潜在的算法问题:

给定一个值为v ₁,...,v _n的硬币系统,有限的硬币库存a ₁,...,a _n和我们需要支付的金额.我们正在寻找一种算法来计算分区x ₁,...,x _n(0 <= x _i <= a _i)x ₁*v ₁ + x ₂*v ₂ + ... + x _n*v _n > = s使得和x ₁ + ... + x _n -R(r)最大化,其中r是变化,即r = x ₁*v ₁ + x ₂*v ₂ +. .. + x _n*v _n - s和R(r)是从收银员返回的硬币数量.我们假设出纳员拥有无限量的所有硬币并且总是返回最小数量的硬币(例如使用SCHOENING等人中解释的贪婪算法).我们还需要确保没有钱的变化,所以最好的解决方案不是简单地给所有的钱(因为在这种情况下解决方案总是最优的).

感谢您的创意投入!

出于习惯,我经常为简单的函数内联函数定义,例如这个(人为的例子)

class PositiveInteger
{
private:
    long long unsigned m_i;
public:
    PositiveInteger (int i);
};

inline PositiveInteger :: PositiveInteger (int i)
: m_i (i)
{
    if (i < 0)
        throw "oops";
}

我一般喜欢分离界面文件和实现文件,但是,这是我习惯于那些我脑子里的声音告诉我的热门可能会受到很多打击的功能.

我知道这个建议是"简介第一"并且我同意但是如果我事先知道编译器会生成相同的最终目标代码,无论是否在编译或链接时内联这些函数,我都可以避免一大堆分析工作.(另外,我相信注入的性能分析代码本身会导致时序的变化,从而影响非常简单的函数的效果,例如上面的那个.)

GCC 5.1刚刚发布了广告LTO(链接时间优化)的改进.他们真的有多好？知道最终可执行文件的哪些功能可以安全地内联不会受到影响？

我想知道我可以用一组数字建立一个数字的次数:

possible_numbers = 1, 2, 4, 8, 16

如果我想要23号我需要

1x 16
0x 8
1x 4
1x 2
1x 1 

Python中是否有内置函数来执行此操作？

编辑:数字固定为1,2,4,8,16,32,64,128.可以进行多种选择.

由于没有功能构建,我会自己编写代码.

以下是我在ruby中实现的shuffle算法:

def shuffle03!(arr)
    len = arr.length
    for i in 0..len-1
        index1 = Random.rand(0..len-1)
        index2 = Random.rand(0..len-1)
        arr[index1], arr[index2] = arr[index2], arr[index1]
    end
end

我通过推算测试了这个算法:

class ShuffleTest
    def initialize(seed)
        len = seed.length
        @count = {}
        for i in 0..len-1
            @count[seed[i]] = Array.new(len, 0)
        end
    end
    def test(arr)
        for i in 0...arr.length
            @count[arr[i]][i] += 1
        end
    end
    def show_count
        return @count
    end
end


def shuffle03!(arr)
    len = arr.length
    for i in 0..len-1
        index1 = Random.rand(0..len-1)
        index2 = Random.rand(0..len-1)
        arr[index1], arr[index2] = arr[index2], …

我想将我的硬币更改功能转换为memoized函数
来做到这一点,我决定使用字典,以便我的dict中的一个键将成为硬币,值将是一个包含所有可以更改"键"的硬币的列表硬币.
我做的是:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0

    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):

        if len(cache)>0 and kinds in cache[a]:
            return 1
        else:
            if(f(a,kinds)==1):
                cache[a]=kinds // or maybe cache[a].append(..)
                return cache[a]+memo(a-kinds[0],kinds)+memo(a,kinds[1:])
    return memo

memC=memoizeChange(change)
kinds=(50,20,10,5,1)
print(memC(10,kinds))

我想得到一些建议,或者可能还有另一种方法可以做到这一点.
谢谢.

编辑
记忆版:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0
    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):
        if not (a,kinds) in cache:
                cache[(a,kinds)]=f(a,kinds)
        return cache[(a,kinds)]
    return memo

change=memoizeChange(change)
print(change(10))

我有一个函数检查数据是否有效(即非负),并应该警告然后退出子.我遇到的问题是警告被抑制了.任何人都可以解释为什么警告被抑制？

#!/usr/bin/perl
use strict;
use warnings;

my $a = b();
print "Function returned $a\n";

sub b
{
    my $a = -1;
    ($a >= 0) || (warn "\$a is negative" && return 0);
    print "Passed negative check\n";
    return 1;
}

我收到的输出是

Function returned 0

这是我对Spoj 11373的解决方案.可乐的疯狂

#include <cstdio>

int main(){
    int T; scanf("%d",&T);

    for(int j = 1; j <= T; j++){
        int n;
        scanf("%d",&n);
        long long sum = 0, small = 0;
        int t;
        for(int i = 0; i < n; i++) {
            scanf("%d",&t);
            sum += t;
            if( sum < small) small = sum;
        }
        printf("Scenario #%d: %lld\n", j, -1*small+1);
    }
}

问题很简单.这个解决方案在Spoj上需要0.12秒,尽管有0.01秒的解决方案.我很好奇可以对此代码进行哪些优化以加快速度.我认为-1*small+1可能会使用逐位操作,但没有找到如何.此外,由于总和可能超过int,我无法摆脱多久.