简约网站版式,网站首页模板免费下载,给窗帘做网站,推广计划文章目录 写在前面代码分析 写在前面
总共是要四份代码#xff0c;好像都是实现背包问题#xff0c;前面三个都比较简单直观#xff0c;朋友上周在机房给我讲解了一下之后#xff0c;我大概弄清楚了#xff0c;这周好像是最后一次算法课了#xff0c;所以明天我得把剩下… 文章目录 写在前面代码分析 写在前面
总共是要四份代码好像都是实现背包问题前面三个都比较简单直观朋友上周在机房给我讲解了一下之后我大概弄清楚了这周好像是最后一次算法课了所以明天我得把剩下的那个实验代码讲一下。还要写之前小组作业的文档还有这个实验的文档。
害其实文档不需要有太大压力吧。改一改就好了。
代码
//模拟退火
//
#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;
}
