首页 > 代码库 > c语言-完全背包问题

c语言-完全背包问题

2024-07-05 10:42:50   225人阅读

完全背包问题

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

分析：

这个算法使用一维数组，先看伪代码：

for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-cost]+weight}

这个伪代码与P01的伪代码只有v的循环次序不同而已。 为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1] [v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的 子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

代码实现：

 1 /****************完全背包**********************/
 2 #include <iostream>
 3 
 4 using namespace std;
 5 const int V=1000;//定义体积
 6 const int T=5;//定义物品的种类
 7 int f[V+1];
 8 int c[]={400,200,500,200,900};
 9 int w[]={3,1,9,7,5};
10 #define INF -65536
11 #define EMPTY
12 int package()
13 {
14     #ifdef EMPTY//条件编译，可以不装满
15     for(int i=0;i<=V;i++)
16     {
17         f[i]=0;
18     }
19     #else//条件编译，必须装满
20     f[0]=0;
21     for(int i=1;i<=V;i++)
22     {
23         f[i]=INF;
24     }
25     #endif
26     for(int i=0;i<T;i++)
27     {
28         for(int v=V;v>=c[i];v--)
29         {
30             f[v]=max(f[v],f[v-c[i]]+w[i]);
31         }
32     }
33     return f[V];
34 }
35 
36 int main()
37 {
38     int temp;
39     for(int i=0;i<T;i++)
40     {
41         cout<<c[i]<<" ";
42     }
43     cout<<endl;
44     for(int i=0;i<T;i++)
45     {
46         cout<<w[i]<<" ";
47     }
48     cout<<endl;
49     temp=package();
50     cout<<temp<<endl;
51     return 0;
52 }

 

 


联系
我们