0/1背包的回溯法 - webdancer's Blog

0/1背包的回溯法

webdancer posted @ 2011年4月08日 03:16 in 算法 with tags 算法 , 1478 阅读

解法：回溯法。

思路：在遍历的子集树的过程中，应该注意筛选出可行的解，同时当有更好的解时，不断地更新最优解。

#include<stdio.h>
#define N 4
 
int x[N];
int p[N];
int w[N];
int c;
int pmax;
int pcur;
int wcur;
 
int bound(int t){
    int i,pr;
    pr=pcur;
    for(i=t;i<N;i++)
        pr+=p[i];
    if(pr>pmax)
        return 1;
    return 0;
}
 
void backtrace(int t){
    int i;
    if(t>=N){
        if(pmax<pcur){
            pmax=pcur;
            for(i=0;i<N;i++)
                printf("%d ",x[i]);
            printf("\n");
        }
    }
    else{
    for(i=1;i>=0;i--){
        x[t]=i;
        if(i){
            if(w[t]+wcur<=c){
            wcur+=w[t];
            pcur+=p[t];
            backtrace(t+1);
            wcur-=w[t];
            pcur-=p[t];
            }
        }
        else if(bound(t))
            backtrace(t+1);
    }
    }
}
 
int main(){
    c=7;
    w[0]=3;
    w[1]=5;
    w[2]=2;
    w[3]=1;
 
    p[0]=9;
    p[1]=10;
    p[2]=7;
    p[3]=4;
 
    backtrace(0);
    printf("the max :%d\n",pmax);
 
    return 0;
}