公司网站建设的目的和意义,用flash做网站建设,盐城做网站的哪家公司好,WordPress渗透思路一、0-1背包问题的描述 下面将使用回溯法、分支界限法、动态规划法来分析和解决此问题。 二、回溯法
#xff08;1#xff09;算法步骤 #xff08;2#xff09;代码如下#xff08;没有裁剪函数#xff09;#xff1a;
用i和n来判断结束与否#xff0c;是因为解空间…一、0-1背包问题的描述 下面将使用回溯法、分支界限法、动态规划法来分析和解决此问题。 二、回溯法
1算法步骤 2代码如下没有裁剪函数
用i和n来判断结束与否是因为解空间结构是完全二叉树用两节点间的边的深度表示物品序号用两节点之间的边的01值表示该物品选择与否。 #includestdio.h
int n, c, bestp;//物品的个数背包的容量最大价值
int p[10000], w[10000], x[10000], bestx[10000];//物品的价值物品的重量x[i]暂存物品的选中情况,物品的选中情况void Backtrack(int i, int cp, int cw)
{ //cw当前包内物品重量cp当前包内物品价值int j;if (in)//回溯结束{if (cpbestp){bestp cp;for (i 0; i n; i)//这里从0开始也无妨因为后面输出是从1开始的 bestx[i] x[i];}}elsefor (j 0; j 1; j){x[i] j;if (cw x[i] * w[i] c){cw w[i] * x[i];cp p[i] * x[i];Backtrack(i 1, cp, cw);cw - w[i] * x[i];cp - p[i] * x[i];}}
}int main()
{int i;bestp 0;printf(请输入背包最大容量:\n);scanf(%d, c);printf(请输入物品个数:\n);scanf(%d, n);printf(请依次输入物品的重量:\n);for (i 1; i n; i)scanf(%d, w[i]);printf(请依次输入物品的价值:\n);for (i 1; i n; i)scanf(%d, p[i]);Backtrack(1, 0, 0);printf(最大价值为:\n);printf(%d\n, bestp);printf(被选中的物品依次是(0表示未选中1表示选中)\n);for (i 1; i n; i)printf(%d , bestx[i]);printf(\n);getchar(); getchar();return 0;
}2、动态规化 #includestdlib.h
#includestdio.hint V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a, int b) //一个大小比较函数用于当总重大于第I行时
{if (a b)return a;else return b;
}void Knap(int n, int w[], int v[], int x[], int C)
{int i, j;for (i 0; i n; i)V[i][0] 0;for (j 0; j C; j)//j居然是离散的V[0][j] 0;for (i 0; i n - 1; i)for (j 0; j C; j)if (jw[i])V[i][j] V[i - 1][j];elseV[i][j] max(V[i - 1][j], V[i - 1][j - w[i]] v[i]);//输出相应的选择物品j C;for (i n - 1; i 0; i--){if (V[i][j]V[i - 1][j]){x[i] 1;j j - w[i];}elsex[i] 0;}printf(选中的物品是:\n);for (i 0; in; i)printf(%d , x[i]);printf(\n);}int main()
{int s;//获得的最大价值int w[4];//物品的重量 重量 价值 和物品的状态 均对应着存到数组中物品从1开始。 int v[4];//物品的价值int x[4];//物品的选取状态 选中则是1 没选中为0 int n, i;int C;//背包最大容量n 4;printf(请输入背包的最大容量:\n);scanf(%d, C);printf(物品数:\n);scanf(%d, n);printf(请分别输入物品的重量:\n);for (i 0; in; i)scanf(%d, w[i]);printf(请分别输入物品的价值:\n);for (i 0; in; i)scanf(%d, v[i]);Knap(n, w, v, x, C);printf(最大物品价值为:\n);printf(%d\n, s);system(pause);return 0;
}
