贪心算法一.部分背包问题

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 //问题表示
 7 int n=5;  
 8 double W=100;    //背包容量
 9 struct nodetype
10 {
11     double w;
12     double v;
13     double p;//p=v/w 单位价值
14     bool operator<(const nodetype &s) const
15     {
16         return p>s.p;  //利用sort将样例按p递减排序(类中成员p的比较大小 并返回bool型的值) 
17      } 
18 };
19 nodetype A[]={{0},{30,65},{20,30},{50,60},{10,20},{40,40}};//下标0不用 
20 
21 void dispA()
22 {
23     for(int i=1;i<=n;i++)
24     cout<<A[i].w<<" "<<A[i].v<<" "<<A[i].p<<endl;
25 }
26 
27 //求解结果表示
28 #define maxn 100
29 double V;//最大价值 
30 double x[maxn]; 
31 
32 void knap()//求解背包问题并返回总价值 
33 {
34     V=0;//V初始化为0
35     double weight=W;//背包中能装入的余下容量 
36     memset(x,0,sizeof(x));
37     int i=1;
38     
39     while(A[i].w<weight)  //物品i能够全部装入时循环
40     {
41         x[i]=1;
42         weight-=A[i].w; 
43         V+=A[i].v;
44         i++;
45     } 
46     
47     if(weight>0)//当余下重量大于0 
48     {
49         x[i]=weight/A[i].w;//物品i的一部分装入
50         V+=x[i]*A[i].v;//累计总价值 
51     }
52 }
53 
54 int main()
55 {
56     cout<<"求解过程："<<endl;
57     for(int i=1;i<=n;i++)
58     A[i].p=A[i].v/A[i].w;
59     cout<<"排序前："<<endl;
60     dispA();
61     
62     sort(A+1,A+n+1);  //A[1...n]排序
63      
64     cout<<"排序后："<<endl;
65     dispA();
66     
67     knap();
68     
69     cout<<"求解结果：";//输出结果
70     
71     cout<<"  x:[";
72     for(int j=1;j<=n;j++)
73     cout<<x[j]<<" "; 
74     cout<<"]"<<endl;
75     cout<<"总价值="<<V<<endl;
76     return 0; 
77 }
贪心算法 一.部分背包问题

贪心算法一.部分背包问题
