下载文档原格式
01背包问题回溯法c语言01背包问题是一个经典的动态规划问题，可以使用回溯法来解决。
在C语言中，我们可以通过递归的方式来实现回溯法解决01背包问题。
首先，让我们来看一下01背包问题的描述：给定n个物品，每个物品有一个重量和一个价值。
现在有一个背包，它能够容纳一定的重量，问如何选择装入背包的物品，使得背包中物品的总价值最大。
接下来，让我们来看一下如何使用回溯法来解决这个问题。
我们可以定义一个递归函数来尝试将每个物品放入背包或者不放入背包，然后找出最优解。
以下是一个简单的C语言代码示例：c.#include <stdio.h>。
#define N 5 // 物品的数量。
#define W 10 // 背包的容量。
int weight[N] = {2, 2, 6, 5, 4}; // 每个物品的重量。
int value[N] = {6, 3, 5, 4, 6}; // 每个物品的价值。
int maxValue = 0; // 最大的总价值。
void backtrack(int index, int currentWeight, int totalValue) {。
if (index == N || currentWeight == W) {。
if (totalValue > maxValue) {。
maxValue = totalValue;}。
return;}。
// 不放入背包。
backtrack(index + 1, currentWeight, totalValue); // 放入背包。
if (currentWeight + weight[index] <= W) {。
backtrack(index + 1, currentWeight +weight[index], totalValue + value[index]);}。
}。
int main() {。
backtrack(0, 0, 0);printf("背包能够容纳的最大总价值为，%d\n", maxValue);return 0;}。
c语⾔-01背包问题01背包问题问题：有N件物品和⼀个容量为V的背包。
第i件物品的费⽤是c[i]，价值是w[i]。
求解将哪些物品装⼊背包可使价值总和最⼤。
分析：这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不放。
⽤⼦问题定义状态：即f[i][v]表⽰前i件物品恰放⼊⼀个容量为v的背包可以获得的最⼤价值。
则其状态转移⽅程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣出来的。
所以有必要将它详细解释⼀下：“将前i件物品放⼊容量为v的背包中”这个⼦问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为⼀个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放⼊容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放⼊剩下的容量为v-c[i]的背包中”，此时能获得的最⼤价值就是f[i-1][v-c[i]]再加上通过放⼊第i件物品获得的价值w[i]。
优化：以上⽅法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上⾯讲的基本思路如何实现，肯定是有⼀个主循环i=1..N，每次算出来⼆维数组f[i][0..V]的所有值。
那么，如果只⽤⼀个数组 f[0..V]，能不能保证第i次循环结束后f[v]中表⽰的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个⼦问题递推⽽来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。
体积价值00 48 610 26 23 57 12算法笔记（c++）--01背包问题 算法笔记（c++）--经典01背包问题算法解释起来太抽象了。
也不是很好理解，最好的办法就是⼀步步写出来。
背包问题的核⼼在于m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i])这个公式理解起来还是有点⿇烦的特别我这种脑⼦笨的⼈。
所以我先上段代码，然后那数据⼀步步分析就⾏了。
先上代码：代码稍微看看就⾏了，关键我下⾯的解释，⾛⼀遍就懂了。
#include <iostream>#include<algorithm>using namespace std;const int N=15;//假设物品最多个数int v[N]={0,8,10,6,3,7,2}; //价格int w[N]={0,4,6,2,2,5,1}; //体积int main(){int m[N][N]={0}; //m[i][j]数组代表在第i件物品,背包容量为j时候能获得最⼤的价值int n=6,c=12;//设物品个数为6，背包容量为12for(int i=1;i<=n;i++) //遍历物品个数{for(int j=1;j<=c;j++)//各种容量情况{if(j>=w[i])//若此时背包容量⼤于当前物品重量//这⾥的m[i-1][j]就是第i-1个物品在j容量下的价值//m[i-1][j-w[i]]这就是i-1个物品时候,背包容量为j-w[i]时候的最⼤价值m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);else//背包容量⼩于当前物品重量m[i][j]=m[i-1][j];//维持第i-1个物品时候的背包重量}}for(int i=1;i<=n;i++){for(int j=1;j<=c;j++){cout<<m[i][j]<<'';}cout<<endl;}return0;}先解释下m[i][[j]的含义就是在i种物品的情况下，包容量为j的情况下，包内的最⼤价值。
基于遗传算法得0-1背包问题得求解摘要:一、前言组合优化问题得求解方法研究已经成为了当前众多科学关注得焦点,这不仅在于其内在得复杂性有着重要得理论价值,同时也在于它们能在现实生活中广泛得应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列得问题都可以归结到组合优化问题中来。
但就是,往往由于问题得计算量远远超出了计算机在有效时间内得计算能力,使问题得求解变为异常得困难。
尤其对于NP 完全问题,如何求解其最优解或就是近似最优解便成为科学得焦点之一。
遗传算法已经成为组合优化问题得近似最优解得一把钥匙。
它就是一种模拟生物进化过程得计算模型,作为一种新得全局优化搜索算法,它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点,奠定了作为21世纪关键智能计算得地位。
背包问题就是一个典型得组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为)2(O n ,传统上采用动态规划来求解。
设w[i]就是经营活动 i 所需要得资源消耗,M 就是所能提供得资源总量,p[i]就是人们经营活动i 得到得利润或收益,则背包问题就就是在资源有限得条件下, 追求总得最大收益得资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)得一般提法就是:已知n 个物品得重量(weight)及其价值(或收益profit)分别为0>i w 与0>i p ,背包得容量(contain)假设设为0>i c ,如何选择哪些物品装入背包可以使得在背包得容量约束限制之内所装物品得价值最大？该问题得模型可以表示为下述0/1整数规划模型:目标函数:∑==ni i i n x c x x x f 121),,(max⎪⎩⎪⎨⎧=∈≤∑=),2,1(}1,0{t .s 1n i x p x w i n i i i i (*) 式中i x 为0-1决策变量,1=i x 时表示将物品i 装入背包中,0=i x 时则表示不将其装入背包中。
遗传算法的01背包问题(c语言)基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。
但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。
尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。
遗传算法已经成为组合优化问题的近似最优解的一把钥匙。
它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。
背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其n O(2)，传统上采用动态规划来求解。
设w[i]是经营活动 i 所需计算复杂度为要的资源消耗，M是所能提供的资源总量，p[i]是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)的一般提法是：已知n个物品的重量（weight）p?00w?，背包的容量（及其价值（或收益profit）分别为contain）假和i i c?0，如何选择哪些物品装入背包可以使得在背包的容量约束限制之设设为i内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：n?x)x?c,?,xf max(x目标函数：ii12n1?i遗传算法的01背包问题(c语言)?p?wx?s.t iii?（*）1?i?x?{0,1}(i?1,2,?n)?i xx?1x?0时n?则表示不将为0-1决策变量，时表示将物品装入背包中，式中i iii其装入背包中。
三、求解背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。
以下是使用C语言实现01背包问题的回溯法代码：```c#include <stdio.h>#include <stdlib.h>// 初始化背包struct knapsack {int maxWeight; // 背包最大承重int *items; // 物品数组int n; // 物品数量};// 定义物品重量、价值和数量int weights[] = {2, 2, 6, 5, 4};int values[] = {6, 3, 5, 4, 6};int quantities[] = {3, 2, 2, 1, 1};// 初始化背包最大承重和当前承重int maxWeight = 10;int currentWeight = 0;// 初始化最大价值为0int maxValue = 0;// 遍历物品数组void traverseItems(struct knapsack *knapsack, int index) { // 对于每个物品，遍历其数量for (int i = 0; i < knapsack->quantities[index]; i++) {// 如果当前物品可以放入背包装且当前承重不超过背包最大承重，计算放入该物品后的总价值，并更新最大价值if (currentWeight + weights[index] <= knapsack->maxWeight) {int currentValue = values[index] * knapsack->quantities[index];if (currentValue > maxValue) {maxValue = currentValue;}}// 回溯，将当前物品从背包装中移除，递归地尝试下一个物品knapsack->quantities[index]--;if (index < knapsack->n - 1) {traverseItems(knapsack, index + 1);}knapsack->quantities[index]++; // 恢复物品数量，以便下次遍历尝试放入其他物品}}// 主函数int main() {// 初始化背包装和物品数组struct knapsack knapsack = {maxWeight, weights, 5};knapsack.items = (int *)malloc(sizeof(int) * knapsack.n);for (int i = 0; i < knapsack.n; i++) {knapsack.items[i] = values[i] * quantities[i]; // 根据价值和数量计算物品价值，并存储在物品数组中}knapsack.n = quantities[4]; // 由于最后一个物品的数量为1，因此只需遍历前n-1个物品即可得到所有可能的结果// 使用回溯法求解01背包问题，返回最大价值traverseItems(&knapsack, 0);printf("The maximum value is %d.\n", maxValue);free(knapsack.items); // 释放内存空间return 0;}```希望以上信息能帮助到你。
c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。
从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。
对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。
约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中，需求出xt 的值。
xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。
0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。
货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。
例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。
店中有n 种不同的货物。
规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。
你的目标是使车中装载的物品价值最大。
当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。
这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。
0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。
在每一步过程中利用贪婪准则选择一个物品装入背包。
一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。
这种策略不能保证得到最优解。
例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。
当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。
而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。
C语⾔动态规划之背包问题详解01背包问题给定n种物品，和⼀个容量为C的背包，物品i的重量是w[i],其价值为v[i]。
问如何选择装⼊背包的物品，使得装⼊背包中的总价值最⼤？（⾯对每个武平，只能有选择拿取或者不拿两种选择，不能选择装⼊某物品的⼀部分，也不能装⼊物品多次）声明⼀个数组f[n][c]的⼆维数组，f[i][j]表⽰在⾯对第i件物品，且背包容量为j时所能获得的最⼤价值。
根据题⽬要求进⾏打表查找相关的边界和规律根据打表列写相关的状态转移⽅程⽤程序实现状态转移⽅程真题演练：⼀个旅⾏者有⼀个最多能装M公⽄的背包，现在有n件物品，它们的重量分别是W1、W2、W3、W4、…、Wn。
它们的价值分别是C1、C3、C2、…、Cn,求旅⾏者能获得最⼤价值。
输⼊描述：第⼀⾏：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);第2…N+1⾏：每⾏两个整数Wi，Ci，表⽰每个物品的质量与价值。
输出描述：仅⼀⾏，⼀个数，表⽰最⼤总价值样例：输⼊：10 42 13 34 57 9输出：12解题步骤定义⼀个数组dp[i][j]表⽰容量为j时，拿第i个物品时所能获取的最⼤价值。
按照题⽬要求进⾏打表，列出对应的dp表。
W[i]（质量）V[i]（价值）01234567891000000000000210011111111133001334444444500135568899790013556991012对于⼀个动态规划问题设置下标时最好从0开始，因为动态规划经常会和上⼀个状态有关系！从上⾯的dp表可以看出来对于⼀个物品我们拿还是不难需要进⾏两步来判断。
第⼀步：判断背包当前的容量j是否⼤于物品当前的质量，如果物品的质量⼤于背包的容量那么就舍弃。
第⼆步：如果背包可以装下这个物品，就需要判断装下该物品获取的最⼤价值是不是⼤于不装下这个物品所获取的最⼤价值，如果⼤于那么就把东西装下！根据这样的思想我们可以得到状态转移⽅程：如果单签背包的容量可以装下物品:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);如果当前背包的容量装不下该物品:dp[i][j]=dp[i-1][j];#include <stdio.h>int max(const int a,const int b){return a>b ? a:b;}int main(){int w[35]={0},v[35]={0},dp[35][210]={0};int n,m;scanf("%d %d",&m,&n);int i,j;for(i=1;i<=n;i++){scanf("%d %d",&w[i],&v[i]);}for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(j>=w[i])//如果当前背包的容量⼤于商品的质量{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//判断是否应该拿下}else//⼤于背包的当前容量{dp[i][j]=dp[i-1][j];}}}for(int k=0;k<=n;k++){for(int l=0;l<=m;l++){printf("%d ",dp[k][l]);}printf("\n");}printf("%d\n",dp[n][m]);}通过运⾏以上程序可以看到最终的输出dp表和我们的预期是相符合的！但是并没有结束，动态规划有⼀个后⽆效性原则(当前状态只与前⼀个状态有关)。
遗传算法求解0-1背包问题。
（步骤）#include "iostream.h"#include "iomanip.h"#include "stdlib.h"#include "math.h"#include "time.h"//定义问题的最大规模#define max 100//问题规模，即共有多少个包int packageNum;//每个包的重量int packageWeight[max];//每个包的价值int packageValue[max];//约束，背包的最大容量int limitWeight;//群体的规模int colonySize;//colonyState[i][k] 表示一个染色体//colonyState[1...colonySize][ 0|1 ] 表示一代群体int colonyState[max][2][max];// currAge 表示当前代的编号// (currAge+1)%2 表示下一代的编号int currAge = 0;//个体评价信息表typedef struct tagIndividualMsg{int index;int value;} IndividualMsg;IndividualMsg individualMsg[max];//////////////////////////////////////////////////////////// // 函数声明void printColonyState( int nextAge );//////////////////////////////////////////////////////////// //初始化群体void colonyInit(){int i , j;int w;for( i = 0 ; i < colonySize ; i++ ){//保证找到一个符合约束的染色体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][currAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][currAge][j];}}}}//对个体进行评价int cmp( const void *a , const void *b ){IndividualMsg *x = (IndividualMsg *)a;IndividualMsg *y = (IndividualMsg *)b;return y->value - x->value;}void individualEstimate(){int i , j;for( i = 0 ; i < colonySize ; i++ ){individualMsg[i].index = i;individualMsg[i].value = 0;for( j = 0 ; j < packageNum ; j++ )individualMsg[i].value += packageValue[j] * colonyState[i][currAge][j]; }qsort( individualMsg , colonySize , sizeof(IndividualMsg) , cmp );}//终止循环的条件bool stopFlag(){//进行n 代进行后停止static int n = 50;if( n-- <= 0 )return true;elsereturn false;}//赌轮选择int gambleChoose(){int wheel[max] = { 0 };int i = colonySize - 1;int choose;wheel[i] = individualMsg[i].value;for( i-- ; i >= 0 ; i-- )wheel[i] = ( individualMsg[i].value + wheel[i+1] ) + colonySize * ( colonySize - i ); int seed = abs( wheel[0] - ( rand() % ( 2 * wheel[0] ) + 1 ) );choose = colonySize - 1;while( seed > wheel[choose] )choose--;// cout<<"----------------------------------------"<<endl;// cout<<"wheel :"<<endl;// for( i = 0 ; i < colonySize ; i++ )// cout<<setw(5)<<wheel[i];// cout<<endl;// cout<<"seed = "<<seed<<endl;// cout<<"choose "<<choose<<endl;return choose;}//交叉void across( int male , int female , int index ){int nextAge = (currAge+1)%2;int i , j , t;int acrossBit = rand() % (packageNum-1) + 1;for( j = 0 ; j < packageNum ; j++ ){colonyState[index][nextAge][j] =colonyState[individualMsg[male].index][currAge][j];colonyState[index+1][nextAge][j] =colonyState[individualMsg[female].index][currAge][j];}for( i = 0 ; i < acrossBit ; i++ ){t = colonyState[index][nextAge][i];colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];colonyState[index+1][nextAge][j] = t;}}//变异void aberrance( int index ){int seed , nextAge;nextAge = (currAge+1)%2;//只有1/3 的概率发生异变seed = rand() % ( packageNum * 3 );if( seed < packageNum )colonyState[index][nextAge][seed] = ( colonyState[index][nextAge][seed] + 1 ) % 2;}//处理死亡个体void dealDeath(){int i , j;int weight , w;int nextAge = (currAge+1)%2;for( i = 0 ; i < colonySize ; i++ ){weight = 0;for( j = 0 ; j < packageNum ; j++ )weight += packageWeight[j] * colonyState[i][nextAge][j];if( weight > limitWeight ){//随机生成新的个体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][nextAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][nextAge][j];}}}}printColonyState( nextAge );}//最优个体保护void saveBest(){int i , j;int min , minp , value;int nextAge = ( currAge+1)%2;min = individualMsg[0].value;minp = -1;for( i = 0 ; i < colonySize ; i++ ){value = 0;for( j = 0 ; j < packageNum ; j++ )value += packageValue[j] * colonyState[i][nextAge][j]; if( value <= min ){min = value;minp = i;}}if( minp >= 0 ){for( j = 0 ; j < packageNum ; j++ ){colonyState[minp][nextAge][j] =colonyState[individualMsg[0].index][currAge][j];}}}//////////////////////////////////////////////////////////// void setProblem(){int i;packageNum = 5;int w[] = { 5 , 4 , 3 , 2 , 1 };int v[] = { 8 , 9 , 3 , 1 , 2 };for( i = 0 ; i < packageNum ; i++ ){packageWeight[i] = w[i];packageValue[i] = v[i];}limitWeight = 13;colonySize = 5;}void printProblem(){int i;cout<<"----------------------------------------"<<endl;cout<<"problem state:"<<endl;cout<<"packageNum = "<<packageNum<<endl;cout<<"limitWeight = "<<limitWeight<<endl;cout<<"Weight: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageWeight[i];cout<<endl;cout<<"Value: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageValue[i];cout<<endl;}void printColonyState( int k ){cout<<"----------------------------------------"<<endl;cout<<"colonyState-->";if( k == currAge )cout<<"currAge:"<<endl;elsecout<<"next age:"<<endl;int i , j;for( i = 0 ; i < colonySize ; i++ ){for( j = 0 ; j < packageNum ; j++ )cout<<setw(2)<<colonyState[i][k][j];cout<<endl;}}void printIndividualMsg(){int i;cout<<"----------------------------------------"<<endl;cout<<"Individual Msg:"<<endl;for( i = 0 ; i < colonySize ; i++ ){cout<<individualMsg[i].index<<"\t"<<individualMsg[i].value<<endl; }}////////////////////////////////////////////////////////////void main(){srand( (unsigned int)time(NULL) );setProblem();printProblem();//初始群体colonyInit();printColonyState( currAge );while( !stopFlag() ){//评价当前群体individualEstimate();//生成下一代for( int i = 0 ; i < colonySize ; i += 2 ){int male = gambleChoose();int female = gambleChoose();across( male , female , i );aberrance( i );aberrance( i + 1 );}//处理死亡个体dealDeath();//最优个体保护saveBest();//现在的下一代变成下一轮的当前代currAge = ( currAge + 1 ) % 2;//printColonyState( currAge );}//输出问题解individualEstimate();cout<<"近似解:"<<endl;int j , w = 0;cout<<setw(10)<<"Value:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<packageValue[j];cout<<endl;cout<<setw(10)<<"Weight:";for( j = 0 ; j < packageNum ; j++ ){w += packageWeight[j] * colonyState[individualMsg[0].index][currAge][j]; cout<<setw(5)<<packageWeight[j];}cout<<endl;cout<<setw(10)<<"Choose:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<colonyState[individualMsg[0].index][currAge][j];cout<<endl;cout<<"limitWeight: "<<limitWeight<<endl;cout<<"总重量: "<<w<<endl;cout<<"总价值: "<<individualMsg[0].value<<endl; }////////////////////////////////////////////////////////////。
0-1背包问题c语言实现问题描述:给定n种物品和一个背包。
物品i的重量为w[i]，其价值为v[i]，背包的容量为c。
应如何选择装入背包的物品，使得装入背包中的物品的总价值最大。
每种物品最多装入一次。
0-1背包问题：对于要装入背包中的物品，只有两种选择：全部装入或者不装入。
背包问题：对于要装入背包中的物品，可以选择装入一部分，不一定要全部装入背包中。
算法分析：使用贪心策略求解此类问题时，首先要选出最优的度量标准。
可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。
显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。
最优的度量标准是单位价值。
背包问题算法思路：1、将各个物品按照单位价值由高到低排序；2、取价值最高者放入背包；3、计算背包的剩余空间；4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。
下面是C语言实现（DEV c++4.9.9.2运行通过）[cpp]#includevoid package(int n,float c,float v[],float w[],float x[]); void package0_1(int n,float c,float v[],float w[],float x[]);int main(void){int n = 3;float c = 20;float v[] = {24,15,25};float w[] = {15,10,18};//已经按照单位价值降序排列float *x;x = (float*)malloc(sizeof(float)*n);printf("******背包*******\n");package(n,c,v,w,x);printf("*******0-1背包******\n");package0_1(n,c,v,w,x);system("PAUSE");}/** 背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）*/void package(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i{x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i{if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}if(i<=n)//还可以放入一个物品的一部分{x[i] = c/w[i];printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);}}/** 0-1背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入）*/void package0_1(int n,float c,float v[],float w[],float x[]) {int i;for(i=0;i{x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i{if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c); }}#includevoid package(int n,float c,float v[],float w[],float x[]); void package0_1(int n,float c,float v[],float w[],float x[]);int main(void){int n = 3;float c = 20;float v[] = {24,15,25};float w[] = {15,10,18};//已经按照单位价值降序排列float *x;x = (float*)malloc(sizeof(float)*n);printf("******背包*******\n");package(n,c,v,w,x);printf("*******0-1背包******\n");package0_1(n,c,v,w,x);system("PAUSE");}/** 背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）*/void package(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i<n;i++){x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i<n;i++){if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}if(i<=n)//还可以放入一个物品的一部分{x[i] = c/w[i];printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);}}/** 0-1背包问题* n:物品个数* c：背包容量* v[]:每个物品的价值* w[]:每个物品的重量（这里已经按照单位价值降序排列）* x[]:物品是否放入背包（0表示不放，1表示全部放入）*/void package0_1(int n,float c,float v[],float w[],float x[]){int i;for(i=0;i<n;i++){x[i] = 0;//初始状态，所有物品都没有被放入背包}for(i=0;i<n;i++){if(w[i] > c){break;}x[i] = 1;c = c - w[i];printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);}}虽然背包问题和0-1背包都具有最优子结构性质，但是背包问题用贪心算法求出来的是最优解，0-1背包问题通过贪心算法得不到最优解，因为无法保证最后能将背包装满，部分闲置的背包空间使总价值降低了。
基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。
但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。
尤其对于NP 完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。
遗传算法已经成为组合优化问题的近似最优解的一把钥匙。
它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。
背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为)2(O n ，传统上采用动态规划来求解。
设w[i]是经营活动 i 所需要的资源消耗，M 是所能提供的资源总量，p[i]是人们经营活动i 得到的利润或收益，则背包问题就是在资源有限的条件下， 追求总的最大收益的资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)的一般提法是：已知n 个物品的重量（weight ）及其价值（或收益profit ）分别为0>i w 和0>i p ，背包的容量（contain ）假设设为0>i c ，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：目标函数：∑==ni i i n x c x x x f 121),,(max Λ⎪⎩⎪⎨⎧=∈≤∑=),2,1(}1,0{t .s 1n i x p x w i n i i i i Λ （*） 式中i x 为0-1决策变量，1=i x 时表示将物品i 装入背包中，0=i x 时则表示不将其装入背包中。
三、求解背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。
动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。
对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。
它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的增长，往往对于求解背包问题的实际问题是不现实的。
使用递归回溯法解决背包问题的优点在于它算法思想简单， 而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有n 2个，因此，随着物件数 n 的增大，其解的空间将以n2级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。
使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。
因此， 我们可以探索使用遗传算法解决物件数较大的背包问题。
四、遗传算法简介遗传算法( Genetic Algorithms ，GA) 是在1975 年首次由美国密西根大学的D 。
J 。
Holland 教授和他的同事们借鉴生物界达尔文的自然选择法则和孟德尔的遗传进化机制基础之上提出的。
经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。
遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。
算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。
它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。
遗传算法的高效性和强壮性可由Holland提出的模式定理( Schema Therem) 和隐式并行性得以解释。
在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论称为遗传算法的基本定理。
遗传算法是通过定义长度短、确定位数少、适应度值高的模式的反复抽样、组合来寻找最佳点，称这些使遗传算法有效工作的模式为积木块，是遗传算法构造答案的基本材料。
但归根到底，要使遗传算法有效工作必须按照遗传算法的模式定理(或积木块假设) 根据具体问题设计合理的编码方案。
在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群的大小、染色体长、交叉率、变异率、最大进化代数等，这些参数对GA 的性能都有很重p = 0.4 要的影响。
在试验中参数一般选取如下：种群大小N= 20~100 ，交叉概率cp = 0.001~0.1 ，最大进化代数maxgen = 100~500。
~0.9 ，变异概率m遗传算法是具有“生成+检测”的迭代过程的搜索算法。
它的基本处理流程如图1所示。
图1、遗传算法的基本流程遗传算法的基本流程描述如下：（1）编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型串（即染色体）结构数据，如将数据9编码为“1001”；（2）初始化种群：定义整数pop_size 作为染色体的个数，并且随机产生pop_size 个染色体作为初始种群；（3）评估种群中个体适应度：评价函数对种群中的每个染色体（chromosome ）求得其个体适应度)(fitness f i ；（4）选择：选择把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；（5）交叉：定义参数c p 作为交叉操作的概率，由（4）选择得到的两个个体以概率c p 交换各自的部分染色体，得到新的两个个体；（6）变异：定义参数m p 作为变异操作的概率，由（5）得到每个个体中的每个基因值都以概率m p 进行变异；（7）演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数（maxgen ）的种群演化，遗传算法终止。
五、背包问题的遗传算法求解描述基于背包问题的模型（*），我们设计了针对于背包问题的染色体编码方法：将待求解的各量X 表示成长为n 的二进制字符串]j [x ，j=1，2， …，n 。
0]j [x =表示物体j 不放入背包内，1]j [x =表示物体j 放入背包内。
例如：111001100…000111代表一个解，它表示将第1、2、3、6、7…n-2,n-1,n 号物体放入背包中，其它的物体则不放入。
根据遗传算法的基本流程，我们确定了求解背包问题的遗传算法：步骤1、初始化过程确定种群规模popsize 、杂交概率c p 、变异概率m p 、染色体长度lchrom及最大进化代数maxgen ；读入背包问题的相关信息，如每个物体的重量weight[j]、每个物体的收益profit[j]和背包的容量contain ，其中1)lchrom (,1,0j -=Λ；1.3 取1)lchrom (,1,0j )1,0(u ]j [x -==Λ，其中)1,0(u 表示0-1整数的均匀分布函数，即随机地生成数0或1，生成的]j [x 串即可看为一个染色体个体。
若不满足模型（*）的约束条件，则拒绝接受，由1.2重新生成一个新的染色体个体chrom ；如果产生的染色体可行，则接受它作为种群的一名成员，经过有限次的1.2抽样后，得到popsize 个可行的染色体chrom ，形成新的种群。
1.4 置种群的代数gen=0；步骤2、计算种群中个体适应度以及统计种群适应度情况2.1 按照下列公式计算种群中个体适应度：)1(1lchrom 0j ]j [chrom *]j [weight weight ∑-==；)2(containifweight )contain weight (*alpha ]j [chrom *]j [profit contain ifweight ]j [chrom *]j [profit fitness 1lchrom 0j 1lchrom 0j ⎪⎪⎩⎪⎪⎨⎧>--≤=∑∑-=-= 公式（2）的下半部分即为适应度的惩罚函数，其中参数 1.0alpha >。
2.2 按公式（3）计算种群的总体适应度，)3(]i [fitness sumfitness 1popsize 0i ∑-==并且按照排序的方法统计出种群中的最大、最小适应度的染色体个体，分别标记为maxpop 、minpop ；步骤3、选择操作3.1 生成一个随机数rand_Number ，要求1_0<<Nuber rand ；3.2 按照赌轮法选择个体，赌轮法的算法描述如下：int selection( ){i=0; //个体的编号sum=0； //部分个体适应度的累加和//根据随机数和群体的总适应度确定赌轮的位置wheel-pos=rand_Number*sufitness;while sum<wheel-pos && i<=popsize{ i=i+1;sum=sum+fitness[i]; //fitness 为第i 个个体的适应度}return i-1; //选择了个体i-1}3.3 重复两次操作3.1、3.2，生成两个个体作为交叉操作的父代；步骤四、交叉操作4.1 根据事先定义好的交叉概率c p ，为了确定是否进行交叉操作，则生成[0，1]的随机数pp ，若c p pp <，则进行4.2交叉操作，否则将两个父代保留为下一代的两个个体；4.2 随机生成]1lchrom ,[0-的整数作为交叉点，对两个父代个体交叉生成新的两个个体；4.3 重复pop_size/2次4.1、4.2便可生成pop_size 个个体组成新的种群； 步骤五、 变异操作5.1 根据事先定义好的变异概率m p ，为了确定新种群上的每个个体上的每个基因是否进行变异操作，则生成[0，1]的随机数pp ，若m p pp <，则进行5.2变异操作，否则基因不变异；5.2 基因变异操作为原基因若为1，则新基因则变异为0，若原基因为0，则新基因变异为0；步骤6、 演化6.1 按步骤2的方法计算新种群的个体适应度和总体适应度情况，尤其是找出新种群中最大适应度的个体和最小适应度的个体；6.2 若旧种群的最大个体适应度〉新种群的最大个体适应度，把旧种群的最大适应度的个体代替新种群中的最小适应度的个体，否则进行6.3；6.3 种群的代数gen=genm+1，若gen〉Maxgen，则结束种群的演化，否则转到步骤2。
六、遗传算法求解的实现1、遗传算法的主要参数#define popsize 80 //种群的规模#define pc 0.7 //杂交概率#define pm 0.1 //变异概率#define lchrom 50 //染色体长度#define maxgen 5000 //最大进化代数double alpha; //计算适应度时使用的惩罚函数系数2、数据结构（1）背包信息：//背包问题中物体重量、收益、背包容量int weight[lchrom],profit[lchrom],contain;（2）种群个体结构体struct population{unsigned int chrom[lchrom]; //染色体double fitness; //适应度unsigned int parent1,parent2,cross; //双亲、交叉点};（3）父代种群和新生代种群//父代种群、新生代种群struct population oldpop[popsize],newpop[popsize]; //pop_size为种群大小（4）适应度信息//种群的总适应度、最小、最大适应度double sumfitness,minfitness,maxfitness;//一个种群中最大和最小适应度的个体编号int minpop,maxpop;3、主要函数说明（1）、int read_infor( )功能：从文件knapsack.txt中读出背包信息（物体重量、收益、背包容量）；参数：无；返回值：返回读取文件信息是否正确；流程图：见图2。
