回溯法 0 1背包问题

用回溯法解决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;
}