华师一附中OI组

标题: 经典背包问题 [打印本页]

---

作者: admin    时间: 2018-6-3 12:03
标题: 经典背包问题
假设有5个物品，重量分别是 4 7 8 9 3，价值分别是5 8 10 13 4，能不能在重量不超过x的情况下得到价值的最大值。

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int w[6]= {0,4,7,8,9,3}; //假设有5个物品
   
5. int v[6]= {0,5,8,10,13,4};
   
6. int f[105][6]; //f[x][y] 表示重量不超过x时最大的价值
   
7. int g[105];
   
8. int i,j;
   
9. int t1,t2,t;
   
10. int main()
    
11. {
    
12.     cout<<"\n========way1=========\n";
    
13. 
    
14.     for(i=1; i<=5; i++)
    
15.         for (j=0; j<=100; j++)
    
16.         {
    
17.             if (j>=w[i])  ///这样写很清晰吧！
    
18.             {
    
19.                 t1=f[j-w[i]][i-1]+v[i];
    
20.                 t2=f[j][i-1];
    
21.                 t=max(t1,t2);
    
22.             }
    
23.             else t=f[j][i-1];
    
24.             f[j][i]=t;
    
25.         }
    
26. 
    
27.     for (i=1; i<=5; i++)
    
28.     {
    
29. 
    
30.         for (j=0; j<=13; j++) cout<<setw(4)<<f[j][i];
    
31.         cout<<'\n';
    
32.     }
    
33. 
    
34. 
    
35.     cout<<"\n========way2=========\n";
    
36.     g[0]=0;
    
37.     for (i=1; i<=5; i++)
    
38.     {
    
39.         for (j=100; j>=w[i]; j--)
    
40.         {
    
41.             if (j>=w[i])
    
42.             {
    
43.                 t1=g[j-w[i]]+v[i];
    
44.                 t2=g[j];
    
45.                 t=max(t1,t2);
    
46.             }
    
47.             g[j]=t;
    
48. 
    
49.         }
    
50.         for (j=0; j<=13; j++) cout<<setw(4)<<g[j];
    
51.         cout<<endl;
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2