动态规划(二)上机实验报告

动态规划

1、 01背包问题

2、 #include

3、 #include

4、 using namespace std;

5、

6、 int v_[10000][10000]; //前i个物品装入容量为j的背包中的最大价值

7、 int x[10000]; //装入背包的物品

8、

9、 int KnapSack(int w[], int v[], int n, int c){

10、 int i,j;

11、

12、 //初始化第0行和第0列

13、 for(i=0; i<=n; ++i)

14、 v_[i][0] = 0;

15、 for(j=0; j<=c; ++j)

16、 v_[0][j] = 0;

17、

18、 //计算第i行

19、 for(i=1; i<=n; ++i)

20、 for(j=1; j<=c; ++j)

21、 if(j

22、 v_[i][j] = v_[i-1][j];

23、 else

24、 v_[i][j] = v_[i-1][j] > v_[i-1][j-w[i]]+v[i]

25、 ? v_[i-1][j] : v_[i-1][j-w[i]]+v[i];

26、

27、 //计算装入背包的物品

28、 for(j=c,i=n; i>0; --i)

29、 if(v_[i][j]>v_[i-1][j]){

30、 x[i] = 1;

31、 j = j-w[i];

32、 }else

33、 x[i] = 0;

34、

35、 //返回最大价值

36、 return v_[n][c];

37、 }

38、

39、 int main(){

40、 //w重量 v价值 n物品数 c背包容量

41、 int w[10000],v[10000];

42、 int n,c;

43、 cin>>c>>n;

44、 for(int i=1; i<=n; ++i)

45、 cin>>w[i]>>v[i];

46、 cout<

47、 }

48、最大子段和

49、 #include

50、 #include

51、 using namespace std;

52、

53、 int main()

54、 {

55、 int n;

56、 int a[100000];

57、 int b[100000];

58、 cin>>n;

59、 for(int i=0; i

60、 cin>>a[i];

61、 b[i] = a[i];

62、 }

63、 int max_ = 0;

64、 for(int i=0; i

65、 b[i] = max(b[i],b[i-1]+a[i]);

66、 if(max_

67、 max_ = b[i];

68、 }

69、 cout<

70、 return 0;

71、 }

72、 K-近似匹配

73、 #include

74、 #include

75、 #include

76、 using namespace std;

77、

78、 int d[10000][10000];

79、

80、 int min(int a, int b, int c){

81、 int min = a

82、 if(c

83、 min = c;

84、 return min;

85、 }

86、

87、 int ASM(string p, int m, string t, int n){

88、 int i,j;

89、

90、 //初始化

91、 for(j=1; j<=n; ++j)

92、 d[0][j] = j;

93、 for(i=0; i<=m; ++i)

94、 d[i][0] = i;

95、

96、 //依次计算

97、 for(j=1; j<=n; ++j)

98、 for(i=1; i<=m; ++i)

99、 if(p[i-1] == t[j-1])

100、 d[i][j] = min(d[i-1][j-1], d[i-1][j]+1, d[i][j-1]+1);

101、 else

102、 d[i][j] = min(d[i-1][j-1]+1, d[i-1][j]+1, d[i][j-1]+1);

103、

104、 //返回最小差别数

105、 return d[m][n];

106、 }

107、

108、 int main(){

109、 //p[]存储模式 t[]存储文本

110、 //char p[10000],t[10000];

111、 int m,n;

112、

113、 string p,t;

114、 cin>>p>>t;

115、 m = p.length();

116、 n = t.length();

117、

118、 // cin>>m;

119、 // for(int i=1; i<=m; ++i)

120、 // cin>>p[i];

121、

122、 // cin>>n;

123、 // for(int i=1; i<=n; ++i)

124、 // cin>>t[i];

125、

126、 cout<

127、 return 0;

128、 }

129、最优二叉树查找

130、 #include

131、 #include

132、 #include

133、 using namespace std;

134、

135、 int c[10000][10000];

136、

137、 int OptimalBST(int p[], int n){

138、 int i,j,k,d;

139、 int min,sum;

140、

141、 //初始化主对角线和第一条次对角线

142、 for(int i=1; i<=n; ++i){

143、 c[i][i-1] = 0;

144、 c[i][i] = p[i-1];

145、 }

146、 c[n+1][n] = 0;

147、

148、 //计算其余对角线

149、 for(d=1; d

150、 for(i=1; i<=n-d; ++i){

151、 j = i+d;

152、 min = 99999777;

153、 //mink = i;

154、 sum = 0;

155、 for(k=i; k<=j; ++k){

156、 sum += p[k-1];

157、 if(c[i][k-1]+c[k+1][j]

158、 min = c[i][k-1]+c[k+1][j];

159、 }

160、 }

161、 c[i][j] = min+sum;

162、 }

163、

164、 ////////////////////////////

165、 // for(i=0; i<=n; ++i){

166、 // for(j=0; j<=n; ++j)

167、 // cout<

168、 // cout<

169、 // }

170、

171、 return c[1][n];

172、 }

173、

174、 int main(){

175、 //n个字符的查找概率存储在p[]中

176、 int p[10000];

177、 int n;

178、

179、 cin>>n;

180、 int del=0;

181、 for(int i=0; i

182、 cin>>p[i];

183、 del+=p[i];

184、 }

185、

186、 cout<

187、 }

1、 01背包问题

2、最大子段和

3、 K-近似匹配

4、最优二叉树查找

1、我一开始把二叉查找树那里的一些数据类型搞错了，导致出现了一些错误（数据类型不匹配）。

2、最优二叉树查找里面我没有将double改成int导致结果出错了，这个低级错误耗了我好长好长时间QAQ。