用回溯法解决01背包问题C语言实现

#include<stdio.h> int x[100]; //数组用来存放每个物品的状态是0 还是1 int val[100] = {-1};//存放每个物品的价值 int weight[100] = {-1};//存放每个物品的重量 int IsOverLoad(int n, int c)//判断物品是否超重 { int i, w = 0; for(i=0; i<n; i++) { w = w + x[i] * weight[i]; } if(w > c) return 1;//超重 else return 0; } int GetVal(int n)//返回所有物品的价值和 { int i, v = 0; for(i=0; i<n; i++) { v = v + x[i] * val[i]; } return v; } void Knap_1(int n, int flag, int c, int *price)//找到物品的装包的最高的价值量 { int i, p; if(IsOverLoad(n, c) == 1)//超过背包的装载上限c，剪枝 return; if(n == flag)//搜索完一条可能的解的路径 { p = GetVal(n);//获得这种装包的方案的总价值量 if(*price < p) { *price = p;//price 为各种方案中的最高的价值量 } return;//回溯 } for(i=1; i>=0; i--) { x[n] = i;//生成可能的解路径 Knap_1(n+1, flag, c, price);//递归调用 } } void Knap_2(int n, int flag, int c, int price) { int i, j, p; if(IsOverLoad(n, c) == 1) return; if(n == flag) { p = GetVal(n); if(price == p) { printf("--------------------bag-------------------\n"); for(j=0; j<n; j++) { if(x[j] == 1) { printf("| |p%d: | |\n", j); printf("| |weight:%2d kg | |\n", weight[j]); printf("| |price: %2d $ | |\n\n", val[j]); } } printf("------------------------------------------\n\n"); return;//回溯法继续搜索 } return;//回溯法继续搜索 } for(i=1; i>=0; i--) { x[n] = i; Knap_2(n+1, flag, c, price); } } void main() { int price = 0, n, c, i; printf("Input the number of products:\n"); scanf("%d", &n); printf("Input the weight of each produce:\n"); for(i=0; i<n; i++) scanf("%d", &weight[i]); printf("Input the price of each produce:\n"); for(i=0; i<n; i++) scanf("%d", &val[i]); printf("Input the limit of the bag can overload:\n"); scanf("%d", &c); Knap_1(0, n, c, &price); Knap_2(0, n, c, price); printf("The grass price :%d $\n", price); getch(); }