- 注册时间
- 2004-10-13
- 最后登录
- 2019-5-15
⑧专业
*永恒国度*
- 积分
- 14145
|
图中给出3件物品(n), C是背包的容量,W,V就是1~n件物品的重量和价值。
相近的解题方法如下:- #include<iostream>
- using namespace std;
- class Knap
- {
- friend int Knapsack(int p[],int w[],int c,int n);
- public:
- void print()
- {
- for(int m=1;m<=n;++m)
- cout << bestx[m] << " ";
- cout << endl;
- }
-
- private:
- int Bound(int i);
- void Backtrack(int i);
- int c; //背包容量
- int n; //物品数
- int *w;//物品重量数组
- int *p;//物品价值数组
- int cw;//当前重量
- int cp;//当前价值
- int bestp;//当前最优值
- int *bestx;//当前最优解
- int *x;//当前解
- };
- int Knap::Bound(int i)
- {
- //计算上界
- int cleft = c - cw;//剩余容量
- int b = cp;
-
- //以物品单位重量价值递减序装入物品
- while(i<=n && w[i]<=cleft)
- {
- cleft -= w[i];
- b += p[i];
- ++i;
- }
- //装满背包时
- if(i<=n) b += p[i]/w[i]*cleft;
- return b;
- }
- void Knap::Backtrack(int i)
- {
- if(i>n)
- {
- if(bestp<cp)
- {
- for(int j=1;j<=n;++j)
- bestx[j] = x[j];
- bestp = cp;
- }
- return;
- }
- if(cw+w[i]<=c) //搜索左子树
- {
- x[i] = 1;
- cw += w[i];
- cp += p[i];
- Backtrack(i+1);
- cw -= w[i];
- cp -= p[i];
- }
- if(Bound(i+1)>bestp) //搜索右子树
- {
- x[i] = 0;
- Backtrack(i+1);
- }
- }
- class Object
- {
- friend int Knapsack(int p[],int w[],int c,int n);
- public:
- int operator<=(Object a) const
- {
- return (d>=a.d);
- }
- private:
- int ID;
- float d;
- };
- int Knapsack(int p[],int w[],int c,int n)
- {
- int W = 0;
- int P = 0;
- int i = 1;
- Object *Q = new Object[n];
-
- for(i=1;i<=n;++i)
- {
- Q[i-1].ID = i;
- Q[i-1].d = 1.0*p[i]/w[i];
- P += p[i];
- W += w[i];
- }
- if(W<=c)
- return P; //装入所有物品
- //依物品单位重量排序
- float f;
- for(i=0;i<n;++i)
- for(int j=i;j<n;++j)
- {
- if(Q[i].d<Q[j].d)
- {
- f = Q[i].d;
- Q[i].d = Q[j].d;
- Q[j].d = f;
- }
- }
-
- Knap K;
- K.p = new int[n+1];
- K.w = new int[n+1];
- K.x = new int[n+1];
- K.bestx = new int[n+1];
- K.x[0] = 0;
- K.bestx[0] = 0;
- for(i=1;i<=n;++i)
- {
- K.p[i] = p[Q[i-1].ID];
- K.w[i] = w[Q[i-1].ID];
- }
- K.cp = 0;
- K.cw = 0;
- K.c = c;
- K.n = n;
- K.bestp = 0;
- //回溯搜索
- K.Backtrack(1);
- K.print();
- delete[] Q;
- delete[] K.w;
- delete[] K.p;
- return K.bestp;
- }
- int main(void)
- {
- int *p;
- int *w;
- int c=0;
- int n=0;
- int i=0;
-
- cout << "请输入物品个数n:" << endl;
- cin >> n;
- p = new int[n+1];
- w = new int[n+1];
- p[0] = 0;
- w[0] = 0;
-
- cout << "请输入n个物品的价值:" << endl;
- for(i=1;i<=n;++i)
- cin >> p[i];
-
- cout << "请输入N个物品的重量:" << endl;
- for(i=1;i<=n;++i)
- cin >> w[i];
-
- cout << "请输入背包容量:" << endl;
- cin >> c;
-
- cout << Knapsack(p,w,c,n) << endl;
- system("PAUSE");
- return 0;
- }
复制代码 还是比较多不懂的地方,像类里面的Bound方法最后那句://装满背包时
if(i<=n) b += p/w*cleft;
第i物品的价值/第i物品的重量*背包剩余容量是什么意思?
在这个IF之前的循环不是已经把重量都得到了吗?
还有就是它到底是怎么分别左右子树的? 晕晕的 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
|