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

0/1背包的回溯法

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

解法:回溯法。

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

 

#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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee