软件设计师考试考点分析与真题详解的目录

比特培训-24期(2017年上)-软件设计师培训课件，免费下载

2ocw

比特培训-24期(2017年上)-软件设计师培训课件|002015年-2016年试题及解析|14多媒体和知识产权(2017年下半年-打印版本)-软设doc|13网络安全(2017年上半年-打印版本-改革版本)docx|12数据库打印版本（2017年上格式ok）docx|11面向对象设计模式--打印版本(2017年上-Java版本-24期)docx|10UML分析与设计(2017年上-第24期打印版本)doc|09面向对象及Java实践(2017年上--完整打印版本）docx|08 *** 作系统原理与技术（打印版本-2017年上-24期）doc|07常用算法设计方法(2017年上-打印版本--邓少勋--有答案--改革版本)docx|06计算机体系结构-打印版本(24期-2017年上)docx|05数据结构(2017年上-打印版本)docx|04数据流图与数据库分析与设计(2017年上-打印版本)doc|03程序设计语言基础和编译原理(2017年上半年-打印版本)doc|02计算机网络概述打印版(2017年上)docx。

背包问题是一个非常有名的问题。可以这样叙述如下。假设有 n 件物品，记为 d1,d2,d3,…… dn。对于每一种物品di (1=<i=<n), 它的重量是wi ,而它的价值为 vi。现在要求用这 n 种物品的子集填满背包，使其总重量不超过给定的重量限制 TOT，并使得背包的价值尽可能高。

1实数背包

物品可以一部分放在背包中，那么直接贪心就行了，把物品按性价比(v[i]/w[i])升序放入即为最优解。

复杂度O(n+nlogn)

2整数背包

物品只能整个放入背包，不允许拆开放，用动态规划求解。

dp[i,j]表示前i个物品放入容量为j的背包中可以得到的最优解。

状态转移方程：dp[i,j]=max{dp[i-1,j],dp[i-1,j-w[i]]+v[i]}

复杂度O(nm)

3多重背包

与1、2不同，这里有k个背包，每个背包有不同的容量，其它一样。

没什么好办法，只能搜索。

对于每个物品i，枚举它能被放在背包j，也可以不放物品i。

复杂度O(kn)

可以针对不同的题目采取不同的剪枝。

背包问题数学模型为(由于输入问题,下标很难输入规范,如c1中1是下标,请注意)

maxZ=c1x1+c2x2++cnxn

w1x1+w2x2++wnxn<=W

xi>=0,且为整数,i=1,2,,n

式中：

ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。

动态规划的有关要素如下:

阶段k：第k次装载第k种物品（k=1,2,…,n）

状态变量sk：第k次装载时背包还可以装载的重量(或体积)

决策变量xk：第k次装载第k种物品的件数

决策允许集合：Dk(sk)={dk|0 xksk/wk，xk为整数}

状态转移方程：sk+1=sk－wkxk

阶段指标：vk=ckxk

一般来说，用来解决背包问题的方法有递归法和贪心法等，但用这两中方法来解决背包问题都有其不可避免的缺点，递归法虽能遍历搜索空间，找到最优解，但由于此问题的解的空间是以2的N级增长的，所以它只适用于解决小规模的背包问题，而贪心法又很难真正找到最优解，此方法找到的最优解往往与真正的最优解相差很远。而遗传算法作为一种随机的优化与搜索方法，具有良好的并行性，而且遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因此适用于任何规模。遗传算法的高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性。

（如果你是需要计算机编程序的话，答案内容就更多些，现在不晓得你应用背包问题做什么呢）

#include<stdioh>

int i,j,n,C,w[100],v[100],x[100],V[100][100];

int KnapSack();

void main()

{

printf("请输入背包的容量:");

scanf("%d",&C);

printf("请输入物品的个数:");

scanf("%d",&n);

printf("请输入物品的重量:");

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

scanf("%d",&w[i]);

printf("请输入物品的价值:");

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

scanf("%d",&v[j]);

printf("最大价值为:%d\n",KnapSack());

}

int KnapSack()

{

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

V[i][0]=0;

for(j=0;j<=C;j++)

V[0][j]=0;

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

for(j=1;j<=C;j++)

if(j<w[i])

V[i][j]=V[i-1][j];

else

{

if(V[i-1][j-w[i]]+v[i]>V[i-1][j])

V[i][j]=V[i-1][j-w[i]]+v[i];

else

V[i][j]=V[i-1][j];

}

j=C;

for(i=n;i>0;i--)

{

if(V[i][j]>V[i-1][j])

{

x[i]=1;

j=j-w[i];

}

else

x[i]=0;

}

return V[n][C];

}

以上就是关于软件设计师考试考点分析与真题详解的目录全部的内容，包括:软件设计师考试考点分析与真题详解的目录、我想知道运筹学中旅行背包问题。谢谢！、0/1背包问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！