C语言-二维背包问题

二维费用背包问题

问题:

二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有 一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和 b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。

 

分析:

费用加了一维,只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是:

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量v和u采用逆序的循环,当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了,相信有了前面的基础,你能够自己实现出这个问题的程序。

 

代码实现:

C语言-二维背包问题
 1 /***************二维背包问题*******************/
 2 #include <iostream>
 3 
 4 using namespace std;
 5 #define EMPTY
 6 #define INF -66536
 7 const int V=1000;//容器体积
 8 const int U=1000;
 9 const int T=5;//物品种类
10 int f[V+1][U+1];
11 int v[T]={400,600,200,800,100};
12 int u[T]={600,300,100,200,500};
13 int w[T]={5,4,1,9,3};
14 /*int v[5]={100,200,200,800,700};//代价1
15 int u[5]={300,400,600,700,100};//代价2
16 int w[5]={5,8,11,9,4};//价值*/
17 int package()
18 {
19     #ifdef EMPTY
20     for(int i=0;i<=V;i++)
21     {
22         for(int j=0;j<=U;j++)
23         {
24             f[i][j]=0;
25         }
26     }
27     #else
28     f[0][0]=0;
29     for(int i=1;i<=V;i++)
30     {
31         for(int j=1;j<=U;j++)
32         {
33             f[i][j]=INF;
34         }
35     }
36     #endif // EMPTY
37     for(int i=0;i<T;i++)
38     {
39         for(int v1=V;v1>=v[i];v1--)
40         {
41             for(int u1=U;u1>=u[i];u1--)
42             {
43                 f[v1][u1]=max(f[v1][u1],f[v1-v[i]][u1-u[i]]+w[i]);
44             }
45         }
46     }
47     return f[V][U];
48 }
49 int main()
50 {
51     int temp;
52     temp=package();
53     cout<<temp<<endl;
54     return 0;
55 }
C语言-二维背包问题

 

C语言-二维背包问题,布布扣,bubuko.com

C语言-二维背包问题

上一篇:01背包问题python实现


下一篇:java开始到熟悉103-104