c语言-完全背包问题

完全背包问题

问题：有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的顺序循环。这就是这个简单的程序为何成立的道理。

代码实现：

/****************完全背包**********************/
#include <iostream>

using namespace std;
const int V=1000;//定义体积
const int T=5;//定义物品的种类
int f[V+1];
int c[]={400,200,500,200,900};
int w[]={3,1,9,7,5};
#define INF -65536
#define EMPTY
int package()
{
    #ifdef EMPTY//条件编译，可以不装满
    for(int i=0;i<=V;i++)
    {
        f[i]=0;
    }
    #else//条件编译，必须装满
    f[0]=0;
    for(int i=1;i<=V;i++)
    {
        f[i]=INF;
    }
    #endif
    for(int i=0;i<T;i++)
    {
        for(int v=V;v>=c[i];v--)
        {
            f[v]=max(f[v],f[v-c[i]]+w[i]);
        }
    }
    return f[V];
}

int main()
{
    int temp;
    for(int i=0;i<T;i++)
    {
        cout<<c[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<T;i++)
    {
        cout<<w[i]<<" ";
    }
    cout<<endl;
    temp=package();
    cout<<temp<<endl;
    return 0;
}