首页 > 代码库 > 01背包问题回溯法和动态规划

01背包问题回溯法和动态规划

2024-07-14 01:08:51   222人阅读

 

题目要求：

输入背包的容量v和物品的数量n；接下来n 行每行输入两个数字,第一个是物品质量，第二个是物品价值；

输出背包容纳物品的最大价值。

下面直接贴代码：

回溯法

 1 #include<iostream>//之前必须知道背包容量和n个物品  2 #include<algorithm> 3 using namespace std; 4 class Property 5 { 6     public:  7     int weight,profit; 8     double average; 9     friend bool operator<(Property a,Property b)10     {11         return a.average>b.average;12     }13 };14 class Pack15 {16     public:17         Pack(int Q,int n)//构造函数，初始化 18         {19             capcity=Q;20             number=n;21             property=new Property[n+1];22             bestp=cw=cp=0;23         }24         ~Pack()25         {26             delete []property;27         }28         void inputproperty()29         {30             for(int i=0;i<number;i++)31             {32                 cin>>property[i].weight>>property[i].profit;33                 property[i].average=1.0*property[i].profit/property[i].weight;34             }35             sort(property,property+number);36         }37         int command()38         {39             int totalweight=0;40             int totalvalue=http://www.mamicode.com/0;41             for(int i=0;i<number;i++)42             {43             totalweight+=property[i].weight;44             totalvalue+=property[i].profit;45             }46             if(totalweight<capcity)return totalvalue;47             backtrack(0);48             return bestp;49         }50         bool bound(int i)51         {52             int currentp=cp;53             int currentw=capcity-cw;54             while(currentw>=property[i].weight&&i<number)55             {56                 currentw-=property[i].weight;57                 currentp+=property[i].profit;58                 i++;59             }60             if(i<number)61             currentp+=1.0*property[i].profit*currentw/property[i].weight;62             return currentp>bestp;63         }64         void backtrack(int i)65         {66             if(i>number-1)67             {68                 if(bestp<cp)69                 bestp=cp;70                 return;71             }72             if(cw+property[i].weight<=capcity)//此处必须用<=比较符号，不然会错 73             {74                 cw+=property[i].weight;75                 cp+=property[i].profit;76                 backtrack(i+1);77                 cw-=property[i].weight;78                 cp-=property[i].profit;79             }80             if(bound(i+1));81             backtrack(i+1);82         }83     private:84     int capcity,number;    85     Property *property;86     int cw,cp,bestp; 87 };88 int main()89 {90     int n,m;91     while(cin>>n>>m)92     {93         Pack object(n,m);94         object.inputproperty();95         cout<<object.command()<<endl;96     }97     return 0;98 }

输入：

20 5
4 7
5 8
2 10
5 10
8 16

输出：
44

动态规划法

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int main() 5 { 6     int Capcity,weight; 7     int *w,*p; 8     int profit[200][200]; 9     while(cin>>Capcity>>weight)10     {11         memset(profit,0,sizeof(profit));12         w=new int[weight+1];13         p=new int[weight+1];14         for(int i=1;i<=weight;i++)15         cin>>w[i]>>p[i];//输入重量和价值 16         for(int i=1;i<=weight;i++)17         {18             for(int j=1;j<=Capcity;j++)19             {20                 if(w[i]>j)profit[i][j]=profit[i-1][j];21                 else if(profit[i-1][j]<profit[i-1][j-w[i]]+p[i])22                 profit[i][j]=profit[i-1][j-w[i]]+p[i];23                 else profit[i][j]=profit[i-1][j];24             }25         }26         for(int i=1;i<=weight;i++)27         {28         for(int j=1;j<=Capcity;j++)29         {30             cout<<profit[i][j]<<" ";31         }32         cout<<endl;    33         }34     }35     return 0;36 }

 


联系
我们