問題描述：

設有1g，2g，3g，5g，10g，20g的砝碼各若干枚（其總重≤1000g），要求：

輸入：

a1???a2???a3???a4???a5???a6(表示1g砝碼有a1個，2g砝碼有a2個，......20g砝碼有a6個)

輸出：

Total=N (N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況)

輸入樣例：1??1??0???0???0???0

輸出樣例：Total=3，表示可以稱出1g，2g，3g三種不同的重量

動態規劃求解：

從砝碼1開始分析，假設前i個砝碼能稱出的不同重量為Q[i],那么Q[i]一定是這樣計算出來的：在Q[i-1]的基礎上，對Q[i-1]個不同的重量，分別添加k個砝碼i，再添加的過程中除去重復情況。

假設：w[N]表示N個不同重量的砝碼（例子中N=6），w[0~N-1]。

????? c[N]表示N個不同砝碼相應的數量，c[1~N]。

則：Q[i] = (Q[i-1] + k*w[i])-添加過程中重復的個數。其中0=<k<=c[i]。

定義一個輔助布爾型數組visit[M+1],這里的M是例子中的1000，表示最大重量不超過M。

visit[j]=1表示，重量為j的情況已經存在，否則表示重量為j的情況還未出現。其中visit[0]作為一個多余空間存在，可以作為一個臨時變量。最后遍歷visit[1~M]，統計1的個數就得到不同重量的個數。

通過這個輔助數組，就可以除去重復情況，實現如下：

?

[cpp]?view plaincopy

1?#include?<iostream>??

?2?using?namespace?std;??

?3?#define?N?6??

?4?#define?M?1000??

?5?int?w[N]={1,2,3,5,10,20};??

?6?int?c[N]={0};??

?7?int?visit[M+1]?=?{0};??

?8???

?9?int?weight_count()??

10?{??

11?????????int?i?=?0;??

12?????????int?j?=?0;??

13?????????int?total?=?0;??

14?????????int?count?=0;??

15???

16?????????visit[0]?=?w[0]*c[0];//visit[0]用于每添加一個砝碼時遍歷的結束位置??

17?????????for(i?=?1;i<=c[0];i++)??

18?????????????????visit[w[0]*i]?=?1;//初始化visit[1~c[0]],表示已經添加了砝碼1??

19?????????for(i?=?1;i<N;i++)??

20?????????{??

21?????????????????int?m?=?visit[0];??

22?????????????????for(int?k?=?1;k<=c[i];k++)??

23?????????????????{??

24?????????????????????????for(j?=?0;j<=m;j++)??

25?????????????????????????{??

26?????????????????????????????????if(j+?k*w[i]>M)??

27?????????????????????????????????????????break;??

28??????????????????????????????????if(visit[j]?==?1?&&?visit[j?+?k*w[i]]?!=?1?||?j==0)??

29??????????????????????????????????{??

30?????????????????????????????????????????visit[j?+?k*w[i]]?=?1;??

31?????????????????????????????????????????total?=?j+k*w[i];??

32??????????????????????????????????}??

33?????????????????????????}??

34?????????????????}??

35?????????????????visit[0]?=?total;??

36?????????}??

37?????????for(i?=?1;i<=M;i++)??

38?????????{??

39?????????????????if(visit[i]==1)??

40?????????????????{??

41?????????????????????????cout?<<?i?<<?"?";??

42?????????????????????????count?++;??

43?????????????????}??

44?????????}??

45?????????return?count;??

46???

47?}??

48?int?main()??

49?{??

50?????????int?i?=?0;??

51?????????for(i?=?0;i<N;i++)??

52?????????????????cin?>>c[i];??

53?????????int?count?=?weight_count();??

54?????????cout?<<?count?<<?endl;??

55?}??

總結

以上是生活随笔為你收集整理的求连续子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。