背包问题:
给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。
背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集
实验数据： 背包容量为10 给定4个物品，重量为{7，3，4，5} 对应的价值为：{42，12，40，25}
输出的结果 选中重量为4，5的物品 总价值为65
#include<iostream> using namespace std; int c; //背包的容量 int bag_values=0;//背包（装入）的价值 初始化为0 int goods_num; //货物数 int maxValue = -1; //定义最大的价值 int calc_arrangement(); //函数 在后面实现 struct things { int weight; int value; //这个是用来计算 全排列的时候那些结果是由哪些下标的货物计算而来 int innerindex[10]; }goods[1001]; //直接计算所有货物的全排列 int calc_arrangement() { int head = 1; int tail = goods_num + 1; //tail指向的是最后一个元素的后一位 while (head <= goods_num) { for (int i = head + 1; i <= tail - 1; i++) { if (goods[i].innerindex[head] != 1) //就是说这个要与head的相加值的 其获得时候 并没有head的值参与其中 { goods[tail].value = goods[head].value + goods[i].value; goods[tail].weight = goods[head].weight + goods[i].weight; //因为现在的这个goods[tail]的值的由来goods[i]参与了进来 // 所以要把参与goods[i]的其他index标识到goods[tail]之中 for(int temp=1;temp<=goods_num;temp++) goods[tail].innerindex[temp] = goods[i].innerindex[temp]; goods[tail].innerindex[head] = 1; tail++; } else continue; } head++; } int index=-1; for (int j = tail - 1; j > 0; j--) { if (goods[j].weight <= c) { if (goods[j].value > maxValue) { maxValue = goods[j].value; index = j; } } else continue; } return index; } int main() { cout << "请输入背包的容量："; cin >> c; cout << "请输入货物的数量："; cin >> goods_num; cout << "请输入每个货物的重量及其对应的价值："; for (int i = 1; i <= goods_num; i++) { cin >> goods[i].weight; cin >> goods[i].value; goods[i].innerindex[i] = 1; } int index=calc_arrangement(); cout <<"总价值为："<< maxValue<<endl; for (int j = 1; j <= 4; j++) { if (goods[index].innerindex[j] != 0) cout << "选中的是物品的重量为" << goods[j].weight << " 它的价值为：" << goods[j].value<<endl; } return 0; }