蛮力法0/1背包问题实验
实验项目1 蛮力法
实验题目 使用蛮力法解决0/1背包问题。
问题描述：给定n个重量(weight)为{w1, w2, … ,wn}、价值(key)为{v1, v2, … ,vn}的物品和一个**容量为C(contain)**的背包，求这些物品中的一个最有价值的子集，且要能够装到背包中。
eg:示例：
背包容量C=15kg
物品1：重量2kg，价值2$
物品2：重量12kg，价值4$
物品3：重量1kg，价值2$
物品4：重量1kg，价值1$
物品5：重量4kg，价值10$
实验目的
- 理解算法的时间复杂度；
- 熟练设计和生成问题的解空间：设计一种穷举策略将物品装入背包的各种装法都找出来，并能够在计算机中存储和表示。
- 理解蛮力法的局限性；
- 实验要求
- 掌握用递归或循环生成n个元素的全部子集的算法设计方法；
按上图示例数据求解出问题的一个最优解：装入哪几个物品价值最大，总重量和总价值各是多少？
蛮力法的主要框架
// 辅助数组，防止递归死循环
int visited[5] = { 0 };
// w容量,key价值,len:weight数组长度 depth 深度
void backpack(int w, int* weight, int* key, int len, int depth, int tempSum) {// 如果到达物品数组的末尾 地柜出口if (depth == len) {return;}// 不选择当前物品visited[depth] = 0;backpack(w, weight, key, len, depth + 1, tempSum);// 如果能选择当前物品（背包容量足够）visited[depth] = 1; // 选择当前物品backpack(w - arr[depth], weight, key, len, depth + 1, tempSum + key[depth]); // 递归调用
}
不难看出使用的是递归的方式
算法代码
#include<stdio.h>// 辅助数组，防止递归死循环
int visited[5] = { 0 };
// 寻找最大值
int sumMax = 0;
//
int weightSum = 0;
// 寻找最大值对应装填方式
int method[5] = { 0 };
int capacity = 15; // 背包容量
int count = 0;
//判断容量是否合理
int LessCapacity(int len,const int* arr){int sumWeight = 0;for (int i = 0; i < len; ++i) {if(visited[i] == 1)sumWeight += arr[i];}
// 满足小于等于15 为 1return sumWeight<=capacity ? 1:0;
}
// 遍历当前状态，更新最大价值和装填方式
void Traverse(int* arr, int len, int tempSum, int depth) {printf("--------------------------------------------\n");int weight = 0;// 打印当前状态printf("重量: ");for (int i = 0; i < len; ++i) {printf("%d ", arr[i]);}printf("\n");printf("选择: ");for (int i = 0; i < len; i++) {printf("%d ", visited[i]);if(visited[i]){weight+=arr[i];}}printf("\n");printf("当前总重量: %d\n", weight);printf("当前总价值: %d\n", tempSum);if(weight>capacity){printf("该情况不符合要求!\n");}else{printf("该情况符合要求!\n");}printf("--------------------------------------------\n\n");// 如果当前价值大于已知的最大价值，则更新最大价值和method数组if (tempSum > sumMax && LessCapacity(len,arr)) {sumMax = tempSum;
// 更新选择方法for (int i = 0; i < len; i++) {method[i] = visited[i];}}}// 背包问题的递归函数
void backpack(int w, int* arr, int* key, int len, int depth, int tempSum) {// 如果到达物品数组的末尾或背包容量已满，则遍历当前状态if (depth == len) {count++;Traverse(arr, len, tempSum, depth);return;}// 不选择当前物品visited[depth] = 0;backpack(w, arr, key, len, depth + 1, tempSum);// 如果能选择当前物品（背包容量足够）visited[depth] = 1; // 选择当前物品backpack(w - arr[depth], arr, key, len, depth + 1, tempSum + key[depth]); // 递归调用
}
// 判断重量<=15int main() {// 重量int weight[] = { 2, 12, 1, 1, 4 };// 重量对应的价值int key[] = { 2, 4, 2, 1, 10 };backpack(capacity, weight, key, 5, 0, 0); // 调用背包问题的递归函数printf("----------------------------------分隔符----------------------------------\n");printf("总共有%d种情况\n",count);printf("重量: ");for (int i = 0; i < sizeof(weight)/sizeof (int); ++i) {printf("%d ", weight[i]);}printf("\n");printf("选择: ");for (int i = 0; i < sizeof(weight)/sizeof (int); i++) {printf("%d ", method[i]);if(method[i] == 1){weightSum+=weight[i];}}printf("\n 最终重量:%d",weightSum);printf("\n 最终最优金额:%d",sumMax);return 0;
}