背包系列第二讲之完全背包

一段时间没写文章，这两天整了下有关完全背包的内容，跟小伙伴们分享下。
一、问题描述
在N种物品中选取若干件（同一种物品可多次选取）放在空间为V的背包里，每种物品的体积为v₁，v₂，…，v_n，与之相对应的价值为w₁,w₂，…，w_n。求解怎么装物品可使背包里物品不超过背包容量，且总价值最大。
二、基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][V]表示前i种物品恰放入一个容量为V的背包的最大权值，用k表示当前容量下可以装第i种物品的件数，那么k的范围应该是0≤k≤V/v[i]。同样的，我们仍然可以按照每种物品不同的策略写出状态转移方程：
$f[i][V] = max\left\{f[i-1][V],f[i-1][V - k * v[i]] + k * w[i]\right\} (0<=k*v[i]<=V)$
三、基本算法
代码实现如下所示：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int N;                  //物品个数
    int V;                  //背包容量
    cout<<"输入物品的个数及背包的容量:";
    cin>>N>>V;
    vector<int> v(N+1);     //存储物品的体积，第一个位置空出来 
    vector<int> w(N+1);     //存储物品的价值，第一个位置空出来
    vector<vector<int> > F(N+1,vector<int>(V+1)); //DP表，初始化数组默认填充为0 
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i];
    } 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            for (int k = 0; k * v[i] <= j; k++) {
                /*如果能放下*/
                if(v[i]<=j){
                    F[i][j]=max(F[i-1][j],F[i-1][j-k*v[i]]+k*w[i]);
                    /*要么不取，要么取0件、取1件、取2件……取k件*/
                }else{
                    /*放不下的话*/
                    F[i][j]=F[i-1][j];
                    /*继承前i个物品在当前空间大小时的价值*/
                }
            }
        }
    }
    for(int i=0;i<=N;i++){
        for(int j=0;j<=V;j++){
            cout<<F[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"最大价值是："<<F[N][V]<<endl; 
    return 0;
}

程序运行截图：

二维数组实现

四、算法优化

状态转移方程换形

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int N;                  //物品个数
    int V;                  //背包容量
    cout<<"输入物品的个数及背包的容量:";
    cin>>N>>V;
    vector<int> v(N+1);     //存储物品的体积，第一个位置空出来 
    vector<int> w(N+1);     //存储物品的价值，第一个位置空出来
    vector<vector<int> > F(N+1,vector<int>(V+1)); //DP表
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i];
    } 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            for (int k = 0; k * v[i] <= j; k++) {
                /*如果能放下*/
                if(v[i]<=j){
                    F[i][j]=max(F[i-1][j],F[i][j-v[i]]+w[i]);
                    /*要么不取，要么取0件、取1件、取2件……取k件*/
                }else{
                    /*放不下的话*/
                    F[i][j]=F[i-1][j];
                    /*继承前i个物品在当前空间大小时的价值*/
                }
            }
        }
    }
    for(int i=0;i<=N;i++){
        for(int j=0;j<=V;j++){
            cout<<F[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"最大价值是："<<F[N][V]<<endl; 
    return 0;
}

此时，状态和同层的i相关，状态可以继续压缩，可以从小到大循环。
所以对于 $f[i][V] = max\left\{f[i-1][V],f[i][V - v[i]] +w[i]\right\}$
可以使用一维数组来简化表示为：
$f[V] = max\left\{f[V],f[V - v[i]] +w[i]\right\}$
代码进一步优化，如下所示：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int N;                  //物品个数
    int V;                  //背包容量
    cout<<"输入物品的个数及背包的容量:";
    cin>>N>>V;
    vector<int> v(N+1);     //存储物品的体积，第一个位置空出来 
    vector<int> w(N+1);     //存储物品的价值，第一个位置空出来
    vector<int> F(V+1); //DP表
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i];
    } 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            /*如果能放下*/
            if(v[i]<=j){
                F[j]=max(F[j],F[j-v[i]]+w[i]);
                /*要么不取，要么取0件、取1件、取2件……取k件*/
            }else{
                /*放不下的话*/
                F[j]=F[j];
                /*继承前i个物品在当前空间大小时的价值*/
            }
        }
    }
    for(int i=0;i<=V;i++){
        cout<<F[i]<<" ";
    }
    cout<<endl; 
    cout<<"最大价值是："<<F[V]<<endl; 
    return 0;
}

程序运行截图：

一维数组优化

才疏学浅，假若有错误的地方，还请各位同道中人指点迷津。