数的乘方

1. 2的8次方
2. 4的4次方
3. 8的2此方

利用以上思路来减少乘法次数,3次乘法就可以完成运算

注意点：用模来判断乘方的奇偶性，如果是奇数则再乘以x

public static int Power(int x, int y){    if (y == 0)        return 1;    else if (y == 1)        return x;    else if (y == 2)    {        return x * x;    }    else if (y % 2 == 0)    {        y = y / 2;        return Power(x * x, y);    }    else        return x * Power(x * x, y / 2);} static void Main(string[] args) {     Console.WriteLine(Power(2, 8)); }

简单背包问题

从11,8,7,6,5凑满20放到包里

1. 从包中取出与20比较,如果可以容纳的话就继续加
2. 否则的话则放弃该元素试图放下一个元素.
3. 内部数组到了尽头需要索引+1继续尝试填充
4. 如果到了数组尽头还是没凑满，那么尝试从头开始(索引+1)即头元素11换成8

 

public static void knapsack3(int[] values, int total){    var limit = 0;    var length = values.Length;    for (int i = 0; i < length; i++)    {        limit = values[i];        int inner = i + 1;        for (var index = inner; index < length; index++)        {            var weight = limit + values[index];            if (total == weight)                return;            else if (total > weight)                limit += values[index];            if (index == (length - 1) && inner < length)            {                limit = values[i];                index = inner++;            }        }    }}

递归版本

分成两个部分的循环

public static int knapsack(int[] values, int limit, int start, int inside){    var length = values.Length;    if (start == length) return limit;    var temp = limit;    for (int i = start; i < length; i++)    {        if (inside == 1)        {            //inner loop            Console.Write(string.Format("{0},", values[i]));            if (limit - values[i] == 0)            {                Console.WriteLine("success");                return 0;            }            if (limit - values[i] > 0)                limit -= values[i];        }        else        {            //outer loop            Console.WriteLine(string.Format("{0},", values[i]));            if (0 == knapsack(values, limit - values[i], i + 1, 1))                break;        }    }    if (inside == 1)    {        Console.WriteLine();        knapsack(values, temp, start + 1, 1);    }    return limit;}

test

static void Main(string[] args){    int[] values = {11,8,7,6,5 };    knapsack(values, 20, 0,0);}

组合

看此贴