注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!

C++回溯法解决背包问题代码示范

OC/C/C++ 水墨上仙 2361次浏览 已收录 手机上查看

0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C. 问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题. 第一步 确定解空间:装入哪几种物品 第二步 确定易于搜索的解空间结构: 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录,是否选种物品 第三步 以深度优先的方式搜索解空间,并在搜索的过程中剪枝 我们同样可以使用子集合问题的框架来写我们的代码,和前面子集和数问题相差无几。 转自:http://fuliang.iteye.com/blog/165308/

#include
#include
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;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++回溯法解决背包问题代码示范
喜欢 (0)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
加载中……