湘潭大学软件工程算法设计与分析实验-模拟退火算法

写在前面

总共是要四份代码，好像都是实现背包问题，前面三个都比较简单直观，朋友上周在机房给我讲解了一下之后，我大概弄清楚了，这周好像是最后一次算法课了，所以明天我得把剩下的那个实验代码讲一下。还要写之前小组作业的文档，还有这个实验的文档。

害其实文档不需要有太大压力吧。改一改就好了。

代码

//模拟退火
//
#include <bits/stdc++.h>
using namespace std;
void knapsackSa(int w[], int v[], int n, int M) { //n件物品，其重量和价值分别为w[i]和c[i]，寻找将其装入容量为M的背包中物品的最大价值int i, j, dv, dw;int ans[n]; 	//定义解空间for (i = 0; i < n; i++) { //初始化解为0ans[i] = 0;}int val = 0, wei = 0;	//初始化总价值和总重量float t0 = 500; 	//初始温度，控制参数t的初值float t = t0;		//当前温度float a = 0.95f; 	//衰减因子float e = 0.00001f;	    //终止条件int L = 100 * n; 		//等温迭代次数，即每个温度都要迭代的次数，即生成新解的个数while (t > e) { 		//停止退火for (int k = 0; k < L; k++) {i = rand() % n; 	//随机选取第i件物品->生成新解if (ans[i] == 0) {	//若i不在背包中 (则考虑将i放入背包)if (wei + w[i] <= M) {	//且加入总重量后不超过容量M,则直接放入背包中ans[i] = 1;val = val + v[i];wei = wei + w[i];} else{ j = rand() % n;		//随机拿出物品jwhile (ans[j] == 0) {	//一直找，直到找到一个在背包的物体j = rand() % n;   	}dv = v[i] - v[j];dw = w[i] - w[j];if (wei + dw <= M)	//（拿出j放入i后）总重量后不超过容量Mif (dv > 0 || (exp(dv / t) > (double)(rand() / (double)RAND_MAX))) { //价值差大于0或以exp(dv/T)的接受概率接受新解ans[i] = 1;ans[j] = 0;val = val + dv;wei = wei + dw;}}} else {	//若i在包中，则考虑将i拿出j = rand() % n;    //随机选一个不在包里的物品while (ans[j] == 1) {j = rand() % n;}dv = v[j] - v[i];dw = w[j] - w[i];if(wei + dw <= M)if (dv > 0 || (exp(dv / t) > (double)(rand() / (double)RAND_MAX))) { //价值差大于0或以exp(df/T)的接受概率接受新解ans[i] = 0;ans[j] = 1;val = val + dv;wei = wei + dw;}}}t = t * a; 	//降温}cout << "该0/1背包问题的最优解为： ";for (i = 0; i <= n - 1; i++) cout << ans[i] << " ";cout << endl << "最大总价值为：" << val << endl;
}
int main() {int n, M;//n件物品，其重量和价值分别为w[i]和c[i]，寻找将其装入容量为M的背包中物品的最大价值cout << "请输入物品件数n和背包容量M:" << endl;cin >> n >> M;int w[n],v[n];cout << "请依次输入物品重量和价值:" << endl;for (int i = 0; i < n; i++) {cin >> w[i] >> v[i];}srand((unsigned)time(NULL));	//初始化随机函数种子(播种)，srand((unsigned)time(NULL));是拿系统时间作为种子，由于时间是变化的，种子变化，可以产生不相同的随机数。knapsackSa(w, v, n, M);return 0;
}

分析

这只有几页介绍，应该大概理解一下就好了吧。模拟退火算法表示的是，最开始把系统加热，然后让其冷却，最后得到的就是一个比较稳定的状态。我还是不懂。

模拟退火算法视频

模拟退火算法博客教程

看完了上面两个教程，感觉大概懂了一些了。现在去看一下代码。感觉就是贪心，然后有一定的概率不贪心，设计了一个函数，这个函数的取值是一个概率函数，依照这个概率不贪心。

又加了一些注释，明天对着这个注释给助教讲了。还有就是自己就是太担心了，有些事情可以大胆一点，比如说去给助教讲这个算法，害主要还是自己不是很熟练。反正明天一过去就讲，早点讲不用排队。

//模拟退火
//
#include <bits/stdc++.h>
using namespace std;
void knapsackSa(int w[], int v[], int n, int M) { //n件物品，其重量和价值分别为w[i]和c[i]，寻找将其装入容量为M的背包中物品的最大价值int i, j, dv, dw;int ans[n]; 	//定义解空间for (i = 0; i < n; i++) { //初始化解为0ans[i] = 0;}int val = 0, wei = 0;	//初始化总价值和总重量float t0 = 500; 	//初始温度，控制参数t的初值float t = t0;		//当前温度float a = 0.95f; 	//衰减因子，这里加个 f 表示这个数字是单精度浮点数float e = 0.00001f;	    //终止条件int L = 100 * n; 		//等温迭代次数，即每个温度都要迭代的次数，即生成新解的个数while (t > e) { 		//停止退火for (int k = 0; k < L; k++) {i = rand() % n; 	//随机选取第i件物品->生成新解if (ans[i] == 0) {	//若i不在背包中 (则考虑将i放入背包)if (wei + w[i] <= M) {	//且加入总重量后不超过容量M,则直接放入背包中ans[i] = 1;val = val + v[i];//表示的是当前的背包里面放的总的价值wei = wei + w[i];//表示当前背包里面放的总的重量} else{ //这里表示的意思是 i 放不下，但是抽到了 i 这个物品，那么下面我们要重新找一个物品j = rand() % n;		//随机拿出物品jwhile (ans[j] == 0) {	//一直找，直到找到一个在背包的物体j = rand() % n;   	}//找到之后把 j  拿出来，把 i 放进去，对 j 多少有点不厚道了哈哈哈dv = v[i] - v[j];//这个表示的是差值，或者直接直观理解就好，这样写可能还有点绕dw = w[i] - w[j];if (wei + dw <= M)	//（拿出j放入i后）总重量后不超过容量Mif (dv > 0 || (exp(dv / t) > (double)(rand() / (double)RAND_MAX))) { //价值差大于0或以exp(dv/T)的接受概率接受新解ans[i] = 1;//把 i 放进去ans[j] = 0;//把 j 拿出来val = val + dv;wei = wei + dw;}}} else {	//若i在包中，则考虑将i拿出j = rand() % n;    //随机选一个不在包里的物品while (ans[j] == 1) {j = rand() % n;}dv = v[j] - v[i];//表示的是把这件物品拿出来之后的情况dw = w[j] - w[i];if(wei + dw <= M)//wei 表示的是总重量if (dv > 0 || (exp(dv / t) > (double)(rand() / (double)RAND_MAX))) { //价值差大于0或以exp(df/T)的接受概率接受新解ans[i] = 0;ans[j] = 1;val = val + dv;wei = wei + dw;}}}t = t * a; 	//降温}cout << "该0/1背包问题的最优解为： ";for (i = 0; i <= n - 1; i++) cout << ans[i] << " ";cout << endl << "最大总价值为：" << val << endl;
}
int main() {int n, M;//n件物品，其重量和价值分别为w[i]和c[i]，寻找将其装入容量为M的背包中物品的最大价值cout << "请输入物品件数n和背包容量M:" << endl;cin >> n >> M;int w[n],v[n];cout << "请依次输入物品重量和价值:" << endl;for (int i = 0; i < n; i++) {cin >> w[i] >> v[i];}//拿系统时间作为种子产生随机数srand((unsigned)time(NULL));	//初始化随机函数种子(播种)，srand((unsigned)time(NULL));是拿系统时间作为种子，由于时间是变化的，种子变化，可以产生不相同的随机数。//重量和价值的数组，物品件数，总的能承受的重量knapsackSa(w, v, n, M);return 0;
}