使用回溯法解决背包问题
背包问题，较好的解决方法为动态规划，但是在不考虑其时间和计算复杂度的情况下，可以使用回溯法解决（也挺方便）
思想：
遍历所有的可能结果，不断尝试新的物品，如果总价值大于上一次的总价值，即可更新bestValue变量（在不超过总重量的情况下）
程序结果：
可以输入在当前不超重的情况下的最大价值！
上代码：
#include
#include
#include
using namespace std; //这里解决《背包问题》 extern int lastValue = 0; extern int bestValue = 0; int putIntoBag(int *weight, int *value, int bag, int values, int n, int number, int all) { //重量数组、价值数组、一个空包包、当前包包的价值、要放第几个物品、物品总数、包包总价值 if (bag >= all){ if (lastValue == 0) {//初始化 lastValue = values; bestValue = values; } else { if (values > lastValue) { lastValue = values; bestValue = values; } } return 1; } for (int i = n; i < number; i++) { if ((bag + weight[i]) <= all) { //装进去 bag += weight[i]; values += value[i]; int index = putIntoBag(weight, value, bag, values, i + 1, number, all); if (index) { //回溯 bag -= weight[i]; values -= value[i]; } } } } int main() { int weight[10] = {4,5,7,2,8,3,9,6,1,10};//测试重量 int value[10] = {25,14,15,4,14,5,14,8,1,10};//测试价值 int bag = 0; int values = 0; putIntoBag(weight, value, bag, values, 0, 10, 34);//0为初始物品，10为物品总数，34为总重 cout <<"包包最多可以存放这么多价值的物品："<< bestValue << endl; system("pause"); return 0; }
测试结果：
这里有几组测试数据：（引用一下）
https://blog.csdn.net/miscclp/article/details/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176638.html原文链接：https://javaforall.net
