0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C.
问如何选择装入背包的物品,使得装入背包中物品的总价值最大?
分析:
0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题.
第一步 确定解空间:装入哪几种物品
第二步 确定易于搜索的解空间结构:
可以用数组p,w分别表示各个物品价值和重量。
用数组x记录,是否选种物品
第三步 以深度优先的方式搜索解空间,并在搜索的过程中剪枝
我们同样可以使用子集合问题的框架来写我们的代码,和前面子集和数问题相差无几。
#include<iostream>
#include<algorithm>
using namespace std;
class Knapsack{
public:
Knapsack(double *pp,double *ww,int nn,double cc){
p = pp;
w = ww;
n = nn;
c = cc;
cw = 0;
cp = 0;
bestp = 0;
x = new int[n];
cx = new int[n];
}
void knapsack(){
backtrack(0);
}
void backtrack(int i){//回溯法
if(i > n){
if(cp > bestp){
bestp = cp;
for(int i = 0; i < n; i++)
x[i] = cx[i];
}
return;
}
if(cw + w[i] <= c){//搜索右子树
cw += w[i];
cp += p[i];
cx[i] = 1;
backtrack(i+1);
cw -= w[i];
cp -= p[i];
}
cx[i] = 0;
backtrack(i+1);//搜索左子树
}
void printResult(){
cout << "可以装入的最大价值为:" << bestp << endl;
cout << "装入的物品依次为:";
for(int i = 0; i < n; i++){
if(x[i] == 1)
cout << i+1 << " ";
}
cout << endl;
}
private:
double *p,*w;
int n;
double c;
double bestp,cp,cw;//最大价值,当前价值,当前重量
int *x,*cx;
};
int main(){
double p[4] = {9,10,7,4},w[4] = {3,5,2,1};
Knapsack ks = Knapsack(p,w,4,7);
ks.knapsack();
ks.printResult();
return 0;
}
分享到:
相关推荐
用回溯法解决0-1背包问题 用回溯法解决0-1背包问题,一看就明白,超经典解法。
利用回溯法解0-1背包问题讲解,程序调试VC++6.0通过
回溯法实现0-1背包 C++代码
用回溯法写的0-1背包问题的解决方案,可以输入数据
回溯法 0-1背包问题 计算机算法设计与分析 回溯法 背包问题
VC6.0编译器中用C语言实现回溯法解决0-1背包问题,可以输入多组问题进行求解。
1 [斩尾行动]贪心算法实现哈夫曼...2 用回溯法解决0-1背包问题;比较穷举法、动态规划法、贪心法实现的0-1背包问题; 3 用回溯法编程实现装载问题,比较此装载问题与贪心法装载问题区别,思考不同算法的适用问题类型。
算法设计课程实际之回溯法解决0-1背包问题的原代码以及详解
0-1背包的回溯法求解0-1背包的回溯法求解.rar
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.学习并掌握回溯法 2.利用迭代回溯和递归回溯两种方法解决01背包问题。 预览地址:
这是以前在学校学算法设计时写的程序了,都不太记得了。 是0-1背包的回溯算法。 内附实验报告,详解算法设计过程。
算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
利用分支定界算法描述0-1背包问题、货箱装船问题等。
本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。
回溯法解0-1背包问题
C++编写的0-1背包程序,主要利用回溯法
问题的解空间:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个(最优)解。 b. 回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度...
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现与算法的效率分析。 4) 分支限界法求解问题的一般思路,分支限界法求解本问题的思路及其C/C++程序实现...