2023年8月1日发(作者：)

算法设计与分析：蛮⼒法求解01背包问题由于最近在复习算法设计与分析，所以就想试着完成⼀下书上的代码。描述：背包问题:给定重量分别为,价值分别为的n件物品，和⼀个承重为W的背包。求这些物品中⼀个最有价值的⼦集，并能装到背包中。背包问题的蛮⼒解法是穷举这些物品的所有⼦集，找出能够装到背包中的所有⼦集，并在这些⼦集中找出价值最⼤的⼦集实验数据：背包容量为10给定4个物品，重量为{7，3，4，5}对应的价值为：{42，12，40，25}输出的结果选中重量为4，5的物品总价值为65事先说明个⼈看法：个⼈认为⾃⼰这个⽅法很笨，并且很冗杂，毫⽆美感。同时也搜索了⼀些dalao们的⽅法，有⽤dfs的，也有递归的。但是奈何⾃⼰看不懂，所以就只好⾃⼰想出笨⽅法来做了。代码如下#include#include#includeusing namespace std;int c; //背包的容量int bag_values=0;//背包（装⼊）的价值 初始化为0int goods_num; //货物的数量int maxValue = -1; //定义最⼤的价值int calc_arrangement(); //函数 在后⾯实现struct things{ int weight; int value; //这个是⽤来计算 全排列的时候那些结果是由哪些下标的货物计算⽽来 int innerindex[10] = {0};

}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; //⽤这个来记录我所取得的value最⼤的下标

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 << endl; cout << "请输⼊货物的数量："; cin >> goods_num;

cout << "请输⼊每个货物的重量及其对应的价值："; for (int i = 1; i <= goods_num; i++) { cin >> goods[i].weight; cin >> goods[i].value; //初始化所给数据的innerindex

goods[i].innerindex[i] = 1; } int index=calc_arrangement(); cout <<"总价值为："<< maxValue<

for (int j = 1; j <= 4; j++) { //由于innerindex之中已经记录了这个value值获得的来源 所以可以直接输出 if (goods[index].innerindex[j] != 0) cout << "选中的是物品的重量为" << goods[j].weight << " 它的价值为：" << goods[j].value<

2023年8月1日发(作者：)

算法设计与分析：蛮⼒法求解01背包问题由于最近在复习算法设计与分析，所以就想试着完成⼀下书上的代码。描述：背包问题:给定重量分别为,价值分别为的n件物品，和⼀个承重为W的背包。求这些物品中⼀个最有价值的⼦集，并能装到背包中。背包问题的蛮⼒解法是穷举这些物品的所有⼦集，找出能够装到背包中的所有⼦集，并在这些⼦集中找出价值最⼤的⼦集实验数据：背包容量为10给定4个物品，重量为{7，3，4，5}对应的价值为：{42，12，40，25}输出的结果选中重量为4，5的物品总价值为65事先说明个⼈看法：个⼈认为⾃⼰这个⽅法很笨，并且很冗杂，毫⽆美感。同时也搜索了⼀些dalao们的⽅法，有⽤dfs的，也有递归的。但是奈何⾃⼰看不懂，所以就只好⾃⼰想出笨⽅法来做了。代码如下#include#include#includeusing namespace std;int c; //背包的容量int bag_values=0;//背包（装⼊）的价值 初始化为0int goods_num; //货物的数量int maxValue = -1; //定义最⼤的价值int calc_arrangement(); //函数 在后⾯实现struct things{ int weight; int value; //这个是⽤来计算 全排列的时候那些结果是由哪些下标的货物计算⽽来 int innerindex[10] = {0};

}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; //⽤这个来记录我所取得的value最⼤的下标

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 << endl; cout << "请输⼊货物的数量："; cin >> goods_num;

cout << "请输⼊每个货物的重量及其对应的价值："; for (int i = 1; i <= goods_num; i++) { cin >> goods[i].weight; cin >> goods[i].value; //初始化所给数据的innerindex

goods[i].innerindex[i] = 1; } int index=calc_arrangement(); cout <<"总价值为："<< maxValue<

for (int j = 1; j <= 4; j++) { //由于innerindex之中已经记录了这个value值获得的来源 所以可以直接输出 if (goods[index].innerindex[j] != 0) cout << "选中的是物品的重量为" << goods[j].weight << " 它的价值为：" << goods[j].value<