动态规划找零问题O(nk)

主要思路是，用一个数组coinsUsed[]来保存找i分钱所需的硬币数，（i==maxchange就是我们正在寻找的解），用一个数组lastCoin[]来保存哪一个硬币是最后用来得到最佳找零方案的信息。coins[] 用来记录硬币零钱有哪几种，differentCoins记录下coins[]的长度。maxChange记录最后的要兑换的零钱数。该算法复杂度为O(NK)，N为不同面值的硬币数目，K是我们要找的的零钱数量。

 

 

 

public final class MakeChange
{
    // Dynamic programming algorithm to solve change making problem.
    // As a result, the coinsUsed array is filled with the
    // minimum number of coins needed for change from 0 -> maxChange
    // and lastCoin contains one of the coins needed to make the change.
    public static void makeChange( int [ ] coins, int differentCoins,
                int maxChange, int [ ] coinsUsed, int [ ] lastCoin )
    {
        coinsUsed[ 0 ] = 0; lastCoin[ 0 ] = 1;

        for( int cents = 1; cents <= maxChange; cents++ )
        {
            int minCoins = cents;
            int newCoin  = 1;

            for( int j = 0; j < differentCoins; j++ )
            {
                if( coins[ j ] > cents )   // Cannot use coin j
                    continue;
                if( coinsUsed[ cents - coins[ j ] ] + 1 < minCoins )
                {
                    minCoins = coinsUsed[ cents - coins[ j ] ] + 1;
                    newCoin  = coins[ j ];
                }
            }

            coinsUsed[ cents ] = minCoins;
            lastCoin[ cents ]  = newCoin;
        }
    }

    // Simple test program
    public static void main( String [ ] args )
    {
        // The coins and the total amount of change
        int numCoins = 5;
        int [ ] coins = { 1, 5, 10, 21, 25 };
        int change = 0;

        if( args.length == 0 )
        {
            System.out.println( "Supply a monetary amount on the command line" );
            System.exit( 0 );
        }

        try
          { change = Integer.parseInt( args[ 0 ] ); }
        catch( NumberFormatException e )
        {
            System.out.println( e );
            System.exit( 0 );
        }

        int [ ] used = new int[ change + 1 ];
        int [ ] last = new int[ change + 1 ];

        makeChange( coins, numCoins, change, used, last );

        System.out.println( "Best is " + used[ change ] + " coins" );

        for( int i = change; i > 0; )
        {
            System.out.print( last[ i ] + " " );
            i -= last[ i ];
        }
        System.out.println( );
    }
}

 

评论

1 楼 msn877763580 2011-10-06  

数据结构与问题求解------