1,2,5,10分别做基数 第一种: int i =2/5/10; int cont =0; int sum = 100; cont = sum /i; 第二种: 循环用不同的基数相加,直到Sum=100 会得到不同的方法
for (int i = 0; i <=2; i++) { for (int j = 0; j <= 100 - i * 50; i++) { for (int k = 0; k <= 100 - i * 50 - j * 20; k++) { for (int x = 0; x <= 100 - i * 50 - j * 20 - k * 10; x++) { for (int y = 0; y <= 100 - i * 50 - j * 20 - k * 10 - x * 5; y++) { if (x + 5 * y + 10 * k + 20 * j + 50 * i == 100) { Console.WriteLine("{0}张五十,{1}张20,{2}张10元,{3}张五元,{4}张一元", i, j, k, y, x); } } } } } }
Sub Main() For Y50 = 0 To 1 For Y20 = 0 To 4 For Y10 = 0 To 9 For Y5 = 0 To 19 For Y1 = 0 To 100 For J5 = 0 To 100 For J2 = 0 To 100 'For J1 = 0 To 100 'Next Dim J1 = 100 - Y50 - Y20 - Y10 - Y5 - Y1 - J5 - J2 If J1 >= 0 Then If Y50 * 50 + Y20 * 20 + Y10 * 10 + Y1 + J5 * 0.5 + J2 * 0.2 = 100 Then Console.WriteLine("50元:{0},20元:{1},10元:{2},5元:{3},1元:{4},5角:{5},2角:{6},1角:{7}", Y50, Y20, Y10, Y5, Y1, J5, J2, J1) End If Next Next Next Next Next Next Next End Sub
看代码,可以看出是很简单的程序:using System; using System.Linq;namespace ConsoleApplication1 { class Program { static void Main(string[] args) { var query = from n1 in Enumerable.Range(0, 1) let total1 = n1 * 50m from n2 in Enumerable.Range(0, 9) let total2 = total1 + n2 * 20m where total2 <= 100 from n3 in Enumerable.Range(0, 9) let total3 = total2 + n3 * 10m where total3 <= 100 from n4 in Enumerable.Range(0, 9) let total4 = total3 + n4 * 5m where total4 <= 100 from n5 in Enumerable.Range(0, 9) let total5 = total4 + n5 * 1m where total5 <= 100 from n6 in Enumerable.Range(0, 9) let total6 = total5 + n6 * 0.5m where total6 <= 100 from n7 in Enumerable.Range(0, 9) let total7 = total6 + n7 * 0.2m where total7 <= 100 from n8 in Enumerable.Range(0, 9) let total8 = total7 + n8 * 0.1m where total8 == 100 select new int[] { n1, n2, n3, n4, n5, n6, n7, n8 }; var count = 0; foreach (var r in query) { Console.WriteLine("方案{0}: {1},{2},{3},{4},{5},{6},{7},{8}", ++count, r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]); }; Console.ReadKey(); } } }这几乎没有什么算法意味。
改进了一下, 找到或者超出就 break: class Program { const int N = 100, V = 10000; static readonly int[] a = { 1,2,5,10,20,50,100,200,500,1000,2000,5000 }; static int[] b = new int[a.Length]; static int[] k = new int[a.Length];
static void Main() { for (int i = 0; i < b.Length; i++) b[i] = System.Math.Min(V / a[i], N); for (k[0 ] = 0; k[0 ] <= b[0 ]; k[0 ]++) { if (Print(0 )) break; for (k[1 ] = 0; k[1 ] <= b[1 ]; k[1 ]++) { if (Print(1 )) break; for (k[2 ] = 0; k[2 ] <= b[2 ]; k[2 ]++) { if (Print(2 )) break; for (k[3 ] = 0; k[3 ] <= b[3 ]; k[3 ]++) { if (Print(3 )) break; for (k[4 ] = 0; k[4 ] <= b[4 ]; k[4 ]++) { if (Print(4 )) break; for (k[5 ] = 0; k[5 ] <= b[5 ]; k[5 ]++) { if (Print(5 )) break; for (k[6 ] = 0; k[6 ] <= b[6 ]; k[6 ]++) { if (Print(6 )) break; for (k[7 ] = 0; k[7 ] <= b[7 ]; k[7 ]++) { if (Print(7 )) break; for (k[8 ] = 0; k[8 ] <= b[8 ]; k[8 ]++) { if (Print(8 )) break; for (k[9 ] = 0; k[9 ] <= b[9 ]; k[9 ]++) { if (Print(9 )) break; for (k[10] = 0; k[10] <= b[10]; k[10]++) { if (Print(10)) break; for (k[11] = 0; k[11] <= b[11]; k[11]++) { if (Print(11)) break; }}}}}}}}}}}} }
static bool Print(int m) { int n = 0, v = 0; for (int i = 0; i <= m; i++) n += k[i]; for (int i = 0; i <= m; i++) v += a[i] * k[i]; if (n >= N || v >= V) { if (n == N && v == V) { for (int i = 0; i <= m; i++) if (k[i] > 0) System.Console.Write("{0} * {1}, ", (double)a[i]/100, k[i]); System.Console.WriteLine("Sum={0}", (double)V/100); } return true; } return false; } }
完全输出是不可能的,解的数量太多了(上千万了) 给个算小规模还凑合的。(临时写的,不知道有错没有) 如果只是求解的个数,可以用动态规划。 using System;namespace ConsoleApplication1 { class Program { static int[] Items = new int[]{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 }; static int[] Counter; static int Count; static void Main(string[] args) { Counter = new int[Items.Length]; int sum = 500, count = 100; Count = 0; Solve(count, sum, 0); Console.ReadKey(); } static void Solve(int countRemain, int valueRemain, int currentIndex) { if (countRemain == 0 && valueRemain == 0) { WriteResult(); return; } else if (currentIndex == Items.Length) return; else if (countRemain * Items[currentIndex] < valueRemain) return; int max = valueRemain / Items[currentIndex]; for (int i = 0; i <= max; i++) { Counter[currentIndex] = i; Solve(countRemain - i, valueRemain - i * Items[currentIndex], currentIndex + 1); } } static void WriteResult() { Count++; Console.Write("{0}. ", Count); for (int i = 0; i < Items.Length; i++) if (Counter[i] > 0) Console.Write("{0}:{1} ", Items[i], Counter[i]); Console.WriteLine(); } } }
第一种:
int i =2/5/10;
int cont =0;
int sum = 100;
cont = sum /i;
第二种:
循环用不同的基数相加,直到Sum=100
会得到不同的方法
{
for (int j = 0; j <= 100 - i * 50; i++)
{
for (int k = 0; k <= 100 - i * 50 - j * 20; k++)
{
for (int x = 0; x <= 100 - i * 50 - j * 20 - k * 10; x++)
{
for (int y = 0; y <= 100 - i * 50 - j * 20 - k * 10 - x * 5; y++)
{
if (x + 5 * y + 10 * k + 20 * j + 50 * i == 100)
{
Console.WriteLine("{0}张五十,{1}张20,{2}张10元,{3}张五元,{4}张一元", i, j, k, y, x);
}
}
}
}
}
}
Sub Main() For Y50 = 0 To 1
For Y20 = 0 To 4
For Y10 = 0 To 9
For Y5 = 0 To 19
For Y1 = 0 To 100
For J5 = 0 To 100
For J2 = 0 To 100
'For J1 = 0 To 100
'Next
Dim J1 = 100 - Y50 - Y20 - Y10 - Y5 - Y1 - J5 - J2
If J1 >= 0 Then
If Y50 * 50 + Y20 * 20 + Y10 * 10 + Y1 + J5 * 0.5 + J2 * 0.2 = 100 Then Console.WriteLine("50元:{0},20元:{1},10元:{2},5元:{3},1元:{4},5角:{5},2角:{6},1角:{7}", Y50, Y20, Y10, Y5, Y1, J5, J2, J1)
End If
Next
Next
Next
Next
Next
Next
Next End Sub
1f,2f,5f,1m,2m,5m,1k,2k,5k,10k,20k,50k,100k
少写了J1*0.1 If Y50 * 50 + Y20 * 20 + Y10 * 10 + Y1 + J5 * 0.5 + J2 * 0.2 + J1*0.1= 100 Then Console.WriteLine("50元:{0},20元:{1},10元:{2},5元:{3},1元:{4},5角:{5},2角:{6},1角:{7}", Y50, Y20, Y10, Y5, Y1, J5, J2, J1)
这个方法对于我这种菜鸟最适合了~~ 呵呵...
using System.Linq;namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
var query = from n1 in Enumerable.Range(0, 1)
let total1 = n1 * 50m
from n2 in Enumerable.Range(0, 9)
let total2 = total1 + n2 * 20m
where total2 <= 100
from n3 in Enumerable.Range(0, 9)
let total3 = total2 + n3 * 10m
where total3 <= 100
from n4 in Enumerable.Range(0, 9)
let total4 = total3 + n4 * 5m
where total4 <= 100
from n5 in Enumerable.Range(0, 9)
let total5 = total4 + n5 * 1m
where total5 <= 100
from n6 in Enumerable.Range(0, 9)
let total6 = total5 + n6 * 0.5m
where total6 <= 100
from n7 in Enumerable.Range(0, 9)
let total7 = total6 + n7 * 0.2m
where total7 <= 100
from n8 in Enumerable.Range(0, 9)
let total8 = total7 + n8 * 0.1m
where total8 == 100
select new int[] { n1, n2, n3, n4, n5, n6, n7, n8 };
var count = 0;
foreach (var r in query)
{
Console.WriteLine("方案{0}: {1},{2},{3},{4},{5},{6},{7},{8}", ++count, r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]);
};
Console.ReadKey();
}
}
}这几乎没有什么算法意味。
。
using System.Linq;namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
var query = from n1 in Enumerable.Range(0, 1)
let total1 = n1 * 50m
from n2 in Enumerable.Range(0, (int)((100m - total1) / 20m) + 1)
let total2 = total1 + n2 * 20m
where total2 <= 100
from n3 in Enumerable.Range(0, (int)((100m - total2) / 10m) + 1)
let total3 = total2 + n3 * 10m
where total3 <= 100
from n4 in Enumerable.Range(0, (int)((100m - total3) / 5m) + 1)
let total4 = total3 + n4 * 5m
where total4 <= 100
from n5 in Enumerable.Range(0, (int)((100m - total4) / 1m) + 1)
let total5 = total4 + n5 * 1m
where total5 <= 100
from n6 in Enumerable.Range(0, (int)((100m - total5) / 0.5m) + 1)
let total6 = total5 + n6 * 0.5m
where total6 <= 100
from n7 in Enumerable.Range(0, (int)((100m - total6) / 0.2m) + 1)
let total7 = total6 + n7 * 0.2m
where total7 <= 100
from n8 in Enumerable.Range(0, (int)((100m - total7) / 0.1m) + 1)
let total8 = total7 + n8 * 0.1m
where total8 == 100
select new int[] { n1, n2, n3, n4, n5, n6, n7, n8 };
var count = 0;
foreach (var r in query)
{
Console.WriteLine("方案{0}: {1},{2},{3},{4},{5},{6},{7},{8}", ++count, r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]);
};
Console.ReadKey();
}
}}
using System.Linq;namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
var query = from n1 in Enumerable.Range(0, 1)
let total1 = n1 * 50m
let time1 = n1
from n2 in Enumerable.Range(0, (int)((100m - total1) / 20m) + 1)
let total2 = total1 + n2 * 20m
let time2 = time1 + n2
where total2 <= 100 & time2 <= 100
from n3 in Enumerable.Range(0, (int)((100m - total2) / 10m) + 1)
let total3 = total2 + n3 * 10m
let time3 = time2 + n3
where total3 <= 100 & time3 <= 100
from n4 in Enumerable.Range(0, (int)((100m - total3) / 5m) + 1)
let total4 = total3 + n4 * 5m
let time4 = time3 + n4
where total4 <= 100 & time4 <= 100
from n5 in Enumerable.Range(0, (int)((100m - total4) / 1m) + 1)
let total5 = total4 + n5 * 1m
let time5 = time4 + n5
where total5 <= 100 & time5 <= 100
from n6 in Enumerable.Range(0, (int)((100m - total5) / 0.5m) + 1)
let total6 = total5 + n6 * 0.5m
let time6 = time5 + n6
where total6 <= 100 & time6 <= 100
from n7 in Enumerable.Range(0, (int)((100m - total6) / 0.2m) + 1)
let total7 = total6 + n7 * 0.2m
let time7 = time6 + n7
where total7 <= 100 & time7 <= 100
from n8 in Enumerable.Range(0, (int)((100m - total7) / 0.1m) + 1)
let total8 = total7 + n8 * 0.1m
let time8 = time7 + n8
where total8 == 100 & time8 == 100
select new int[] { n1, n2, n3, n4, n5, n6, n7, n8 };
var count = 0;
foreach (var r in query)
{
Console.WriteLine("方案{0}: {1},{2},{3},{4},{5},{6},{7},{8}", ++count, r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]);
};
Console.Write("所有方案打印完毕......................按任意键结束");
Console.ReadKey();
}
}}
呵呵,结果很“稀疏”!
static void Main(string[] args)
{
for (int i = 0; i <=2; i++)
{
for (int j = 0; j <= 100 - i * 50; i++)
{
for (int k = 0; k <= 100 - i * 50 - j * 20; k++)
{
for (int x = 0; x <= 100 - i * 50 - j * 20 - k * 10; x++)
{
for (int y = 0; y <= 100 - i * 50 - j * 20 - k * 10 - x * 5; y++)
{
for (int m = 0; m <= 100 - i * 50 - j * 20 - k * 10 - x * 5 - y; m++)
{
for (int n = 0; n <= 100 - i * 50 - j * 20 - k * 10 - x * 5 - y - 0.2 * m; n++)
{
if ((y + 5 * x + 10 * k + 20 * j + 50 * i+0.2*m+0.1*n) == 100 && (i+j+k+x+y+m+n==100))
{
Console.WriteLine("{0}张五十,{1}张20,{2}张10元,{3}张五元,{4}张一元,{5}两毛,{6}一毛", i, j, k, x, y,m,n);
}
}
}
}
}
}
}
}看来结果应该没什么问题,就这一种吧
懒得改这个东西了!这个没有什么算法意味,只是要注意提前让total和time参与条件判断,只有这一个注意而已。
1 元数据的确认 1角 2角(以前有的) 5角 1元 2元(以前有的)5元 10 元 20 元 50元
2 算法的解析 可以穷举(循环) 可以回溯(递归) 可以枚举(树)
3 树解法
100
50 50
20 20 10 20 20 10
10 10 ...
4 程序设计
可以使用C c++ 等 代码不列出,需要请联系[email protected]
using namespace std;void main()
{
// int sum;
for(int i1 = 0;i1 <= 2;i1++) //50的多少张
for(int i2 = 0;i2 <= 5;i2++) //20
for(int i3 = 0;i3 <= 10;i3++) //10
for(int i4 = 0;i4 <= 20;i4++) //5
for(int i5 = 0;i5 <= 50;i5++) //2
for(int i6 = 0;i6 <= 100;i6++) //1
for(int i7 = 0;i7 <= 100;i7++) //0.5
for(int i8 = 0;i8 <= 100;i8++) //0.2
for(int i9 = 0;i9 <= 100;i9++) //0.1
// sum = ;
if(i1 * 50 + i2 * 20 + i3 * 10 +i4 * 5 + i5 * 2 + i6 * 1 + i7/2 + i8/5 + i9/10 == 100 && i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 == 100 && i7%2 == 0 && i8%5 == 0 && i9%10 == 0)
//一起等于100,张数也等于100,取余为0是避免int型直接影响正确结果。
{
cout<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<" "<<i5<<" "<<i6<<" "<<i7<<" "<<i8<<" "<<i9<<endl;
}}
哪有我朴实- -我就一个新手。。老老实实的做的那种- -。。求高手指点一下。。哪些地方可以用更好的方式代替。。我的这个太呆板了。。一步一步的爬。。
{ static void Main(string[] args)
{ //double[] Money ={50,20,10,5,2,1,0.5,0.2,0.1};
double[] Money = { 5, 2, 1, 0.5, 0.2, 0.1 };
double MaxCount = 10;
double MaxSum = 10;
double _sum,_count; for (int i0 = 0; i0 * Money[0] <=MaxSum;i0++ )
{
for (int i1 = 0; i1 * Money[1] <= MaxSum; i1++)
{
for (int i2 = 0; i2 * Money[2] <= MaxSum; i2++)
{
for (int i3 = 0; i3 * Money[3] <= MaxSum; i3++)
{
for (int i4 = 0; i4 * Money[4] <= MaxSum; i4++)
{
for (int i5 = 0; i5 * Money[5] <= MaxSum; i5++)
{
_sum=i0 * Money[0] + i1 * Money[1] + i2 * Money[2]+i3*Money[3]+i4*Money[4]+i5*Money[5];
_count=i0 + i1 + i2+i3+i4+i5; //判斷,是否滿足條件
if(_sum==MaxSum && _count==MaxSum)
{
Console.WriteLine("{0}*{1},{2}*{3},{4}*{5},{6}*{7},{8}*{9},{10}*{11}",Money[0],i0,Money[1],i1,Money[2],i2,Money[3],i3,Money[4],i4,Money[5],i5);
continue;
} //判斷,有一個超出條件,則重新進入
if (_sum>MaxSum|| _count>MaxSum)
{
continue;
}
}
}
}
}
}
}
Console.ReadKey();
}
}
這個算法是,10張錢=10元的。
100張錢=100元,再加三個for就行了
{ static void Main(string[] args)
{ //double[] Money ={50,20,10,5,2,1,0.5,0.2,0.1};
double[] Money = { 5, 2, 1, 0.5, 0.2, 0.1 };
double MaxCount = 10;
double MaxSum = 10;
double _sum,_count; for (int i0 = 0; i0 * Money[0] <=MaxSum;i0++ )
{
for (int i1 = 0; i1 * Money[1] <= MaxSum; i1++)
{
for (int i2 = 0; i2 * Money[2] <= MaxSum; i2++)
{
for (int i3 = 0; i3 * Money[3] <= MaxSum; i3++)
{
for (int i4 = 0; i4 * Money[4] <= MaxSum; i4++)
{
for (int i5 = 0; i5 * Money[5] <= MaxSum; i5++)
{
_sum=i0 * Money[0] + i1 * Money[1] + i2 * Money[2]+i3*Money[3]+i4*Money[4]+i5*Money[5];
_count=i0 + i1 + i2+i3+i4+i5; //判斷,是否滿足條件
if(_sum==MaxSum && _count==MaxSum)
{
Console.WriteLine("{0}*{1},{2}*{3},{4}*{5},{6}*{7},{8}*{9},{10}*{11}",Money[0],i0,Money[1],i1,Money[2],i2,Money[3],i3,Money[4],i4,Money[5],i5);
continue;
} //判斷,有一個超出條件,則重新進入
if (_sum>MaxSum|| _count>MaxSum)
{
continue;
}
}
}
}
}
}
}
Console.ReadKey();
}
}
重發一次,上面沒格式了
2.進行了優化
3.結果:
5*0,2*0,1*10,0.5*0,0.2*0,0.1*0
5*0,2*1,1*7,0.5*2,0.2*0,0.1*0
5*0,2*2,1*4,0.5*4,0.2*0,0.1*0
5*0,2*3,1*1,0.5*6,0.2*0,0.1*0
5*0,2*3,1*3,0.5*1,0.2*2,0.1*1
5*0,2*4,1*0,0.5*3,0.2*2,0.1*1
5*0,2*4,1*1,0.5*0,0.2*5,0.1*0
5*0,2*4,1*1,0.5*1,0.2*1,0.1*3
5*1,2*0,1*1,0.5*8,0.2*0,0.1*0
5*1,2*0,1*3,0.5*3,0.2*2,0.1*1
5*1,2*0,1*4,0.5*0,0.2*5,0.1*0
5*1,2*0,1*4,0.5*1,0.2*1,0.1*3
5*1,2*1,1*0,0.5*5,0.2*2,0.1*1
5*1,2*1,1*1,0.5*2,0.2*5,0.1*0
5*1,2*1,1*1,0.5*3,0.2*1,0.1*3
5*1,2*1,1*2,0.5*0,0.2*4,0.1*2
5*1,2*1,1*2,0.5*1,0.2*0,0.1*5
5*1,2*2,1*0,0.5*0,0.2*3,0.1*4
成功次數18,總計算量:21417858
5*0,2*0,1*10,0.5*0,0.2*0,0.1*0
5*0,2*1,1*7,0.5*2,0.2*0,0.1*0
5*0,2*2,1*4,0.5*4,0.2*0,0.1*0
5*0,2*3,1*1,0.5*6,0.2*0,0.1*0
5*0,2*3,1*3,0.5*1,0.2*2,0.1*1
5*0,2*4,1*0,0.5*3,0.2*2,0.1*1
5*0,2*4,1*1,0.5*0,0.2*5,0.1*0
5*0,2*4,1*1,0.5*1,0.2*1,0.1*3
5*1,2*0,1*1,0.5*8,0.2*0,0.1*0
5*1,2*0,1*3,0.5*3,0.2*2,0.1*1
5*1,2*0,1*4,0.5*0,0.2*5,0.1*0
5*1,2*0,1*4,0.5*1,0.2*1,0.1*3
5*1,2*1,1*0,0.5*5,0.2*2,0.1*1
5*1,2*1,1*1,0.5*2,0.2*5,0.1*0
5*1,2*1,1*1,0.5*3,0.2*1,0.1*3
5*1,2*1,1*2,0.5*0,0.2*4,0.1*2
5*1,2*1,1*2,0.5*1,0.2*0,0.1*5
5*1,2*2,1*0,0.5*0,0.2*3,0.1*4
成功次數18,總計算量:185120
class Program
{ static void Main(string[] args)
{ //double[] Money ={50,20,10,5,2,1,0.5,0.2,0.1};
double[] Money = { 5, 2, 1, 0.5, 0.2, 0.1 };
double MaxCount = 10;
double MaxSum = 10;
double _sum,_count;
double _CalcCount = 0;//計算量
double _SuccesCount = 0;//成功次數
#region for循環
for (int i0 = 0; i0 * Money[0] <=MaxSum;i0++ )
{
for (int i1 = 0; i1 * Money[1] <= MaxSum; i1++)
{
for (int i2 = 0; i2 * Money[2] <= MaxSum; i2++)
{
for (int i3 = 0; i3 * Money[3] <= MaxSum; i3++)
{
for (int i4 = 0; i4 * Money[4] <= MaxSum; i4++)
{
for (int i5 = 0; i5 * Money[5] <= MaxSum; i5++)
{
_sum=i0 * Money[0] + i1 * Money[1] + i2 * Money[2]+i3*Money[3]+i4*Money[4]+i5*Money[5];
_count=i0 + i1 + i2+i3+i4+i5; _CalcCount++;
//判斷,是否滿足條件
if (_sum == MaxSum && _count == MaxCount)
{
Console.WriteLine("{0}*{1},{2}*{3},{4}*{5},{6}*{7},{8}*{9},{10}*{11}",Money[0],i0,Money[1],i1,Money[2],i2,Money[3],i3,Money[4],i4,Money[5],i5);
_SuccesCount++;
continue;
} //判斷,有一個超出條件,則重新進入
if (_sum > MaxSum || _count > MaxCount)
{
continue;
}
}
}
}
}
} }
Console.WriteLine("成功次數{0},總計算量:{1}", _SuccesCount, _CalcCount);
#endregion for循環 _CalcCount = 0;
_SuccesCount = 0; #region for優化一
for (int i0 = 0; i0 * Money[0] <= MaxSum; i0++)
{
if ((i0 * Money[0]) + (MaxCount - i0) * Money[1]<MaxSum )//之後不再需要計算(更小的錢*所允許的張數,加總都不夠)
{ continue; } for (int i1 = 0; i1 * Money[1] <= MaxSum; i1++)
{
if ((i0 * Money[0]) + (i1 * Money[1]) + (MaxCount - i0 - i1) * Money[2] < MaxSum)//之後不再需要計算(更小的錢*所允許的張數,加總都不夠)
{ continue; } for (int i2 = 0; i2 * Money[2] <= MaxSum; i2++)
{
if ((i0 * Money[0]) + (i1 * Money[1]) + (i2 * Money[2]) + (MaxCount - i0 - i1 - i2) * Money[3] < MaxSum)//之後不再需要計算(更小的錢*所允許的張數,加總都不夠)
{ continue; } for (int i3 = 0; i3 * Money[3] <= MaxSum; i3++)
{
if ((i0 * Money[0]) + (i1 * Money[1]) + (i2 * Money[2]) + (i3 * Money[3]) + (MaxCount - i0 - i1 - i2 - i3) * Money[4] < MaxSum)//之後不再需要計算(更小的錢*所允許的張數,加總都不夠)
{ continue; } for (int i4 = 0; i4 * Money[4] <= MaxSum; i4++)
{
if ((i0 * Money[0]) + (i1 * Money[1]) + (i2 * Money[2]) + (i3 * Money[3]) + (i4 * Money[4]) + (MaxCount - i0 - i1 - i2 - i3 - i4) * Money[5] < MaxSum)//之後不再需要計算(更小的錢*所允許的張數,加總都不夠)
{ continue; } for (int i5 = 0; i5 * Money[5] <= MaxSum; i5++)
{
_sum = i0 * Money[0] + i1 * Money[1] + i2 * Money[2] + i3 * Money[3] + i4 * Money[4] + i5 * Money[5];
_count = i0 + i1 + i2 + i3 + i4 + i5; _CalcCount++;
//判斷,是否滿足條件
if (_sum == MaxSum && _count == MaxCount)
{
Console.WriteLine("{0}*{1},{2}*{3},{4}*{5},{6}*{7},{8}*{9},{10}*{11}", Money[0], i0, Money[1], i1, Money[2], i2, Money[3], i3, Money[4], i4, Money[5], i5);
_SuccesCount++;
//continue;
break;//用break更合理
} //判斷,有一個超出條件,則重新進入
if (_sum > MaxSum || _count > MaxCount)
{
//continue;
break;//用break更合理
}
}
}
}
}
} }
Console.WriteLine("成功次數{0},總計算量:{1}",_SuccesCount, _CalcCount);
#endregion for優化一
Console.ReadKey();
}
}
for (int 面额20 = 0; 面额20 <= 100; 面额20 ++)
for (int 面额10 = 0; 面额10 <= 100; 面额10 ++)
for (int 面额5 = 0; 面额5 <= 100; 面额5 ++)
for (int 面额2= 0; 面额2 <= 100; 面额2 ++)
for (int 面额1= 0; 面额1 <= 100; 面额1 ++)
for (int 面额0_5 = 0; 面额0_5 <= 100; 面额0_5 ++)
for (int 面额0_2= 0; 面额0_2 <= 100; 面额0_2 ++)
for (int 面额0_1= 0; 面额0_1 <= 100; 面额0_1 ++)
for (int 面额0_05 = 0; 面额0_05 <= 100; 面额0_05 ++)
for (int 面额0_02= 0; 面额0_02 <= 100; 面额0_02 ++)
for (int 面额0_01= 0; 面额0_01 <= 100; 面额0_01 ++)if 面额50+面额20+面额10+面额5+面额2+面额1+面额0_5+面额0_2+面额0_1+面额0_05+面额0_02+面额0_01 =100 &&面额50*50+面额20*20 ......=100 输出
class Program
{
static void Main()
{
int V = 10000;
int N = 100;
int[] a = { 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
int[] b = new int[a.Length];
int[] k = new int[a.Length];
for (int i = 0; i < b.Length; i++) b[i] = System.Math.Min(V / a[i], N);
for (k[0 ] = 0; k[0 ] <= b[0 ]; k[0 ]++)
for (k[1 ] = 0; k[1 ] <= b[1 ]; k[1 ]++)
for (k[2 ] = 0; k[2 ] <= b[2 ]; k[2 ]++)
for (k[3 ] = 0; k[3 ] <= b[3 ]; k[3 ]++)
for (k[4 ] = 0; k[4 ] <= b[4 ]; k[4 ]++)
for (k[5 ] = 0; k[5 ] <= b[5 ]; k[5 ]++)
for (k[6 ] = 0; k[6 ] <= b[6 ]; k[6 ]++)
for (k[7 ] = 0; k[7 ] <= b[7 ]; k[7 ]++)
for (k[8 ] = 0; k[8 ] <= b[8 ]; k[8 ]++)
for (k[9 ] = 0; k[9 ] <= b[9 ]; k[9 ]++)
for (k[10] = 0; k[10] <= b[10]; k[10]++)
{
k[11] = N-k[0]-k[1]-k[2]-k[3]-k[4]-k[5]-k[6]-k[7]-k[8]-k[9]-k[10];
if (k[11] >= 0 && k[11] <= b[11] &&
a[0]*k[0]+a[1]*k[1]+a[2]*k[2]+a[3]*k[3]+a[4]*k[4]+a[5]*k[5]+
a[6]*k[6]+a[7]*k[7]+a[8]*k[8]+a[9]*k[9]+a[10]*k[10]+a[11]*k[11]
== V)
for (int i = 0; i < a.Length; i++)
if (k[i] > 0) System.Console.Write("{0} * {1} ", a[i], k[i]);
}
}
}
{
static void Main()
{
int V = 10000;
int N = 100;
int[] a = { 5000, 2000, 1000, 500, 200, 100, 50, };// 20, 10, 5, 2, 1 };
int[] b = new int[a.Length];
int[] k = new int[a.Length];
for (int i = 0; i < b.Length; i++) b[i] = System.Math.Min(V / a[i], N);
for (k[0 ] = 0; k[0 ] <= b[0 ]; k[0 ]++)
for (k[1 ] = 0; k[1 ] <= b[1 ]; k[1 ]++)
for (k[2 ] = 0; k[2 ] <= b[2 ]; k[2 ]++)
for (k[3 ] = 0; k[3 ] <= b[3 ]; k[3 ]++)
for (k[4 ] = 0; k[4 ] <= b[4 ]; k[4 ]++)
for (k[5 ] = 0; k[5 ] <= b[5 ]; k[5 ]++)
for (k[6 ] = 0; k[6 ] <= b[6 ]; k[6 ]++)
for (k[7 ] = 0; k[7 ] <= b[7 ]; k[7 ]++)
for (k[8 ] = 0; k[8 ] <= b[8 ]; k[8 ]++)
for (k[9 ] = 0; k[9 ] <= b[9 ]; k[9 ]++)
for (k[10] = 0; k[10] <= b[10]; k[10]++)
{
k[11] = N-k[0]-k[1]-k[2]-k[3]-k[4]-k[5]-k[6]-k[7]-k[8]-k[9]-k[10];
if (k[11] >= 0 && k[11] <= b[11] &&
a[0]*k[0]+a[1]*k[1]+a[2]*k[2]+a[3]*k[3]+a[4]*k[4]+a[5]*k[5]
+a[6]*k[6]+a[7]*k[7]+a[8]*k[8]+a[9]*k[9]+a[10]*k[10]+a[11]*k[11]
== V)
{
for (int i = 0; i < a.Length; i++)
if (k[i] > 0) System.Console.Write("{0} * {1}, ", (double)a[i]/100, k[i]);
System.Console.WriteLine("Sum={0}", (double)V/100);
}
}
}
}
int[] a = { 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
class Program
{
const int N = 100, V = 10000;
static readonly int[] a = { 1,2,5,10,20,50,100,200,500,1000,2000,5000 };
static int[] b = new int[a.Length];
static int[] k = new int[a.Length];
static void Main()
{
for (int i = 0; i < b.Length; i++) b[i] = System.Math.Min(V / a[i], N);
for (k[0 ] = 0; k[0 ] <= b[0 ]; k[0 ]++) { if (Print(0 )) break;
for (k[1 ] = 0; k[1 ] <= b[1 ]; k[1 ]++) { if (Print(1 )) break;
for (k[2 ] = 0; k[2 ] <= b[2 ]; k[2 ]++) { if (Print(2 )) break;
for (k[3 ] = 0; k[3 ] <= b[3 ]; k[3 ]++) { if (Print(3 )) break;
for (k[4 ] = 0; k[4 ] <= b[4 ]; k[4 ]++) { if (Print(4 )) break;
for (k[5 ] = 0; k[5 ] <= b[5 ]; k[5 ]++) { if (Print(5 )) break;
for (k[6 ] = 0; k[6 ] <= b[6 ]; k[6 ]++) { if (Print(6 )) break;
for (k[7 ] = 0; k[7 ] <= b[7 ]; k[7 ]++) { if (Print(7 )) break;
for (k[8 ] = 0; k[8 ] <= b[8 ]; k[8 ]++) { if (Print(8 )) break;
for (k[9 ] = 0; k[9 ] <= b[9 ]; k[9 ]++) { if (Print(9 )) break;
for (k[10] = 0; k[10] <= b[10]; k[10]++) { if (Print(10)) break;
for (k[11] = 0; k[11] <= b[11]; k[11]++) { if (Print(11)) break;
}}}}}}}}}}}}
}
static bool Print(int m)
{
int n = 0, v = 0;
for (int i = 0; i <= m; i++) n += k[i];
for (int i = 0; i <= m; i++) v += a[i] * k[i];
if (n >= N || v >= V)
{
if (n == N && v == V)
{
for (int i = 0; i <= m; i++)
if (k[i] > 0) System.Console.Write("{0} * {1}, ", (double)a[i]/100, k[i]);
System.Console.WriteLine("Sum={0}", (double)V/100);
}
return true;
}
return false;
}
}
给个算小规模还凑合的。(临时写的,不知道有错没有)
如果只是求解的个数,可以用动态规划。
using System;namespace ConsoleApplication1
{
class Program
{
static int[] Items = new int[]{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
static int[] Counter;
static int Count; static void Main(string[] args)
{
Counter = new int[Items.Length];
int sum = 500, count = 100;
Count = 0;
Solve(count, sum, 0);
Console.ReadKey();
} static void Solve(int countRemain, int valueRemain, int currentIndex)
{
if (countRemain == 0 && valueRemain == 0)
{
WriteResult();
return;
}
else if (currentIndex == Items.Length)
return;
else if (countRemain * Items[currentIndex] < valueRemain)
return; int max = valueRemain / Items[currentIndex]; for (int i = 0; i <= max; i++)
{
Counter[currentIndex] = i;
Solve(countRemain - i, valueRemain - i * Items[currentIndex], currentIndex + 1);
}
} static void WriteResult()
{
Count++;
Console.Write("{0}. ", Count);
for (int i = 0; i < Items.Length; i++)
if (Counter[i] > 0)
Console.Write("{0}:{1} ", Items[i], Counter[i]); Console.WriteLine();
}
}
}