回溯法之0/1背包问题

时间:2021-03-18 04:23:25

题目描述

已知一个载重为M的背包和n件物品,物品编号从0到n-1。第i件物品的重量为 wi,若将第i种物品装入背包将获益pi,这里,wi>0,pi>0,0<=i<n。所谓0/1背包问题是指在物品不能分割,只能整件装入背包或不装入的情况下,求一种最佳装载方案使得总收益最大。

注:

1、本题请用回溯法解决(要使用限界函数进行剪枝)。

2、所有测试数据均已按pi/wi降序排列。

 

输入

第 1 行中有 2 个正整数 n(n<=50)和M ,表示有 n件物品,背包载重为M(m<=100)。然后输入n个物品的重量,最后输入n个物品的收益值。

 

输出

最佳装载方案的总收益 

c++代码如下:

#include<iostream>
using namespace std;
int n;
int m;
int x[100];
int y[100];
int fp=0;
int Bound( int k, int cp, int cw, int *w, int *p)
{
     int b=cp,c=cw;
     for ( int i=k+1;i<n;i++)
     {
         c+=w[i];
         if (c<m)
             b+=p[i];
         else return (b+(1-(c-m)/w[i])*p[i]);
     }
     return b;
}
void BK( int k, int cp, int cw, int &fp, int *x, int *y, int *w, int *p)
{
     int j;
     int bp;
     if (cw+w[k]<=m)
     {
         y[k]=1;
         if (k<n-1) BK(k+1,cp+p[k],cw+w[k],fp,x,y,w,p);
         if (cp+p[k]>fp&&k==n-1)
         {
             fp=cp+p[k];
             for (j=0;j<=k;j++)
                 x[j]=y[j];
         }
     }
     if (Bound(k,cp,cw,w,p)>=fp)
     {
         y[k]=0;
         if (k<n-1)
             BK(k+1,cp,cw,fp,x,y,w,p);
         if (cp>fp&&k==n-1)
         {
             fp=cp;
             for (j=0;j<=k;j++)
                 x[j]=y[j];
         }
     }
}
int BK( int *x, int *w, int *p)
{
     int y[100]={0};
     int fp;
     BK(0,0,0,fp,x,y,w,p);
     return fp;
}
int main()
{  
     int i;
     int w[100];
     int p[100];
     cin>>n>>m;
     for (i=0;i<n;i++)
         cin>>w[i];
     for (i=0;i<n;i++)
         cin>>p[i];
     cout<<BK(x,w,p);
     return 0;
}
结果:
回溯法之0/1背包问题