公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。 程序输入： 第一行是一个整数m，代表可购买的商品的种类数。 接下来是m个整数，每个1行，分别代表这m种商品的单价。 程序输出： 第一行是一个整数，表示共有多少种方案 第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。


用c#怎么写呀

代码如下，注意输入数据，过多会导致堆栈溢出，唉~~~递归……，有更好的算法望放出共享！
Programs.cs

using System;
using System.Collections.Generic;
using using System.Text;

namespace Goods
{
    class Program
    {
        #region 常量

        private const double Money = 1000;

        #endregion

        #region 全局字段

        private static int          _goodsCount;
        private static List<double> _prices;
        private static List<int>    _goodsCountCritical; 

        #endregion

        static void Main()
        {
            Console.Title = "Goods Solution by ";
            var inputFile = string.Concat(Environment.CurrentDirectory, Path.DirectorySeparatorChar, "Input.txt");
            if (!(File.Exists(inputFile))) return;
            var outputFile = string.Concat(Environment.CurrentDirectory, Path.DirectorySeparatorChar, "Output.txt");

            var sr = new StreamReader(inputFile, Encoding.Default);
            var line = sr.ReadLine();
            if (!(int.TryParse(line, out _goodsCount))) return;
            _prices = new List<double>();
            _goodsCountCritical = new List<int>();
            var counter = new List<int>();
            while (true)
            {
                line = sr.ReadLine();
                if (string.IsNullOrWhiteSpace(line)) break;
                double price;
                if (!double.TryParse(line, out price))
                    continue;
                _prices.Add(price);
                _goodsCountCritical.Add((int)Math.Floor(Money / price));
                counter.Add(0);
            }
            if (_prices.Count != _goodsCount) return;
            var result = GetSulution(counter, _prices);
            var sw = new StreamWriter(outputFile, false);
            sw.WriteLine(result.Count);
            for (var i = 0; i < result.Count;i++ )
            {
                Console.WriteLine(result[i]);
                sw.Write(result[i]);
                if (i < result.Count - 1)
                    sw.WriteLine();
            }
            sw.Close();
            Console.Read();
        }

        static List<string> GetSulution(IList<int> counter, IList<double> prices)
        {
            var goodsCount = counter.Count;
            var result = new List<string>();
            for (var i = 0; i <= _goodsCountCritical[goodsCount - 1]; i++)
            {
                var totalPay = 0d;
                for (var c = 0; c < goodsCount; c++)
                    totalPay += counter[c]*prices[c];
                if (totalPay.Equals(Money))
                {
                    var counterStringArray = new string[goodsCount];
                    for (var c = 0; c < goodsCount; c++)
                        counterStringArray[c] = string.Concat(counter[c], " ");
                    result.Add(string.Concat(counterStringArray).TrimEnd(' '));
                }
                else if (totalPay > Money)
                    break;
                counter[goodsCount - 1]++;
            }
            counter[goodsCount - 1] = 0;
            var bit = goodsCount - 2;
            if (bit >= 0)
            {
                while (true)
                {
                    counter[bit]++;
                    if (counter[bit] > _goodsCountCritical[bit])
                    {
                        counter[bit] = 0;
                        bit--;
                        if (bit < 0)
                            return result;
                    }
                    else break;
                }
                result.AddRange(GetSulution(counter, prices));
            }
            return result;
        }
    }
}

[ 本帖最后由 mmxo 于 2012-11-16 12:06 编辑 ]