中山市建设局网站产品营销策划方案3000字

用回溯法解决0 1背包问题

#include <stdio.h>
#include <stdlib.h>/*用回溯法解决01背包问题,维护的变量有：curState[]: 当前状态中物品是否被选中，若i选中,则curState[i]=1,否则为0.optState[]: 从搜索开始到目前状态中的最优状态。curWeight:  当前的总重量curValue:   当前的总价值maxValue:   最佳状态的价值curDeep:    当前深度N:          总的物品个数capacity:   背包的容量weight[]:   第i个物品的重量为weight[i]value[]:    第i个物品的价值value[i]
*/int N,capacity;
int *weight,*value;
int maxValue = 0;
int *curState,*optState;void backtracking(int curDeep,int curWeight,int curValue){int i;if(curDeep>=N){     //到达叶节点if(curWeight<=capacity && curValue>maxValue){maxValue = curValue;        //更新最大值和最大状态向量for(i=0;i<N;i++){optState[i] = curState[i];}}}else{curState[curDeep] = 1;  //选中if(curWeight+weight[curDeep]<=capacity)backtracking(curDeep+1,curWeight+weight[curDeep],curValue+value[curDeep]);curState[curDeep] = 0;  //不选backtracking(curDeep+1,curWeight,curValue);}
}int main(){int i,tw,tv;printf("input number of object:\n");scanf("%d",&N);printf("input capacity of bag:\n");scanf("%d",&capacity);weight = (int *)malloc(sizeof(int)*N);value = (int *)malloc(sizeof(int)*N);curState = (int *)malloc(sizeof(int)*N);optState = (int *)malloc(sizeof(int)*N);printf("input weight and value,by format: weight value\n");for(i=0;i<N;i++){scanf("%d %d",&tw,&tv);weight[i] = tw;value[i] = tv;}backtracking(0,0,0);printf("%d\n",maxValue);return EXIT_SUCCESS;
}