C++背包算法2014-11-25 14:59:45

( 还没有投票,继续加油! )
分享:
31.3K

在C++中,背包算法的实现,有一个背包,它的最大承重一定,有n个物品,每个物品的重量分别是:w1,w2,。。。wn,选择出所有满足重量组合的元素。
目前我设定的是每个物品的重量都不相同,且在往背包中放物体前,物品的重量没有事先进行排序。我采用了vector作为栈,采用了递归算法实现了这个算法,代码如下:

#include "stdafx.h"
#include <vector>
using namespace std;
int Locality(int Check,int weight[],int EndNO)
{
 int i;
 for (i = 0;i < EndNO;i++)
 {
 if (Check == weight[i])//先定位这个元素
  break;
 }
 return i;
}
bool IsInArray(vector<int>& stack,vector<vector<int>>& qualifies,int weight[],int EndNO)
{
 for (size_t j = 0;j < qualifies.size();j++)
 {
 bool bOut = false;
 for (size_t k = 0;k < qualifies[j].size()&&bOut == false;k++)
 {
  for (size_t i = 0;i <stack.size()&&bOut == false;i++)
  {
  if (stack[i] != qualifies[j][k])
   bOut = true;
  }
 }
 if (bOut == false)
  return true;//找到了原来数组中有
 }
 return false;//原来数组中没有
}
//跳出标志 == true就跳出循环
void StartAnother(int weight[],int baghold,int StartNO,int EndNO,vector<int>& stack,vector<vector<int>>& qualifies,bool& Flag)
{
 if (Flag == true)
 return;
 int CurrNO = StartNO;
 stack.push_back(weight[CurrNO]);
 int CurrSum = 0;
 for (size_t j = 0;j < stack.size();j++)
 {
 CurrSum += stack[j];
 }
 if (CurrSum == baghold)
 {
 qualifies.push_back(stack);
 size_t num = stack.size();
 for (size_t i = 0;i < num;i++)
 {
  int NO = Locality(stack[num - i - 1],weight,EndNO);
  stack.pop_back();//先弹出一个,记录下弹出的元素在数组中的位置
CC:  if (NO == EndNO - 1)//如果弹出的元素是最后一个元素,继续弹出
  {
  if (stack.size() == 0)//如果没有元素可以出栈了,并且这个出栈的元素就是数组中最后一个元素,循环结束
  {
   Flag = true;
   return;
  }
  else
   continue;
  }
  else
  {
  stack.push_back(weight[NO+1]);
  if (IsInArray(stack,qualifies,weight,EndNO) == false)
  {
   stack.pop_back();
   StartAnother(weight,baghold,NO+1,EndNO,stack,qualifies,Flag);
   if (Flag == true)
   return;
  }
  else//数组中有这样的组合
   goto CC;
  }
 }
 }
 else if (CurrSum < baghold)
 {
 if (CurrNO < EndNO - 1)
  StartAnother(weight,baghold,CurrNO+1,EndNO,stack,qualifies,Flag);
 else
 {
  CurrNO = Locality(stack[stack.size() - 1],weight,EndNO);
  stack.pop_back();
  if (CurrNO == EndNO - 1)
  {
  if (stack.size() == 0)
   Flag = true;
  else
  {
   CurrNO = Locality(stack[stack.size() - 1],weight,EndNO);
   stack.pop_back();
  }
  }
  StartAnother(weight,baghold,CurrNO+1,EndNO,stack,qualifies,Flag);
 }
 }
 else
 {
 stack.pop_back();
 if (CurrNO < EndNO - 1)
  StartAnother(weight,baghold,CurrNO+1,EndNO,stack,qualifies,Flag);
 else
 {
  CurrNO = Locality(stack[stack.size() - 1],weight,EndNO);
  stack.pop_back();
  if (CurrNO == EndNO - 1)
  {
  if (stack.size() == 0)
  {
   Flag = true;
   return;
  }
  else
  {
   CurrNO = Locality(stack[stack.size() - 1],weight,EndNO);
   stack.pop_back();
  }
  }
  StartAnother(weight,baghold,CurrNO+1,EndNO,stack,qualifies,Flag);
 }
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 int weight[] = {17,1,8,4,7,5,2,3,9};
 int baghold = 17;//背包容量
 int maxValue = 0;
 vector<int> stack;
 vector<vector<int>> qualifies;
 bool t = false;
 int Sum = sizeof(weight)/sizeof(int);
 StartAnother(weight,baghold,0,Sum,stack,qualifies,t);
 printf("所有满足要求的组合包括:\n");
 for (size_t i = 0;i < qualifies.size();i++)
 {
 for (size_t j = 0;j < qualifies[i].size();j++)
 {
  printf("%d\t",qualifies[i][j]);
 }
 printf("\n");
 }
 getchar();
 return 0;
}






头像

snowcoal
  • C++
  • 背包算法

本文标签:

C++背包算法

收藏到我的私密空间

标题:C++背包算法

作者:柳岸花明

你暂未登录,请登录后才可收藏至您的私密空间 确认取消
雪炭网

键盘操作 更便捷 -雪炭网雪中送炭-乐趣无限

如果本站的内容有幸帮助到了您,建议您了解一下当页的广告内容哦,我们的进步离不开您的支持,Thank you~