动态规划——完全背包问题

前置知识：

01背包问题：动态规划之01背包模型_如何何何的博客-CSDN博客

完全背包问题：

给定一个有一定容量的背包，和 n 个物品，每个物品有无限件；

每个物品有其对应的体积和价值；

问背包最多能装下的物品的最大价值为多少。

输入格式：

第一行两个整数，N，V，分别表示物品数量和背包容积；

接下来有 N 行，每行两个整数 vi , wi 用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式：

输出一个整数，表示最大价值。

思路：

同01背包一样推导，面对第i件物品时，我们可以选0件、选1件、选2件……，那么方程就为：

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] + w[i], f[i - 1][j - 2 * v[i] + 2 * w[i] ......)。

如果这样做的话，就需要加上一层循环来决定选几件物品；

发现：

f[i][j - v[i]] = max(f[i - 1][j - v[i]], f[i - 1][j - 2 * v[i]] + w[i], f[i - 1][j - 3 * v[i]] + 2 * w[i]......)

将 f[i][j-v[i]] 加上 w[i] 之后，就可以替换掉 f[i][j] 方程中选择1件，2件，3件……的所有情况；

所以dp方程优化为：

f[i][j] = max(f[i - 1][j]，f[i][j - v[i]] + w[i])。

代码模板如下：

#include
using namespace std;
const int N=1010;
int n,V;
int f[N][N];
 
int main(){
    cin>>n>>V;
    
    int v,w;
    for(int i=1;i<=n;i++){
        cin>>v>>w;
        for(int j=0;j<=V;j++){
            f[i][j]=f[i-1][j];
            if(j>=v)f[i][j]=max(f[i][j],f[i][j-v]+w);
        }
    }
    
    cout<
    return 0;
}

优化至一维：

和01背包不同，在完全背包中，状态是由本层的左边更新而来的，所以我们应该先把本层左边的状态先更新，所以是从前往后更新的。

代码如下：

#include
using namespace std;
const int N = 1010;
int n, V;
int f[N];
 
int main() {
    cin >> n >> V;
 
    int v, w;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w;
        for (int j = v; j <= V; j++) {
            f[j] = max(f[j], f[j - v] + w);//小于v的默认为上一层的状态
        }
    }
 
    cout << f[V];
    return 0;
}

例题1 . 买书：

买书 - C语言网 (dotcpp.com)

思路：

求方案数，f[i][j] 表示只看前 i 件物品，钱数为 j 的时候的方案数。

买：f[i][j] = f[i][j-v] ；

不买：f[i][j] = f[i-1][j]；

f[i][j]等于两者之和；

注意要初始化f[0][0]=1。

AC代码如下：

//二维
#include
using namespace std;
 
const int N = 1010;
int f[N][N];
int m[] = { 0,10,20,50,100 };//书的下标从1开始
int n;//钱
 
int main() {
    cin >> n;
 
    f[0][0] = 1;
 
    for (int i = 1; i <= 4; i++)
        for (int j = 0; j <= n; j++) {
            f[i][j] += f[i - 1][j];//不买
            if (j >= m[i])f[i][j] += f[i][j - m[i]];//买
        }
 
    cout << f[4][n];
    return 0;
}
 
//一维
#include
using namespace std;
 
const int N = 1010;
int f[N];
int m[] = { 0,10,20,50,100 };//书的下标从1开始
int n;//钱
 
int main() {
    cin >> n;
 
    f[0] = 1;
 
    for (int i = 1; i <= 4; i++)
        for (int j = m[i]; j <= n; j++)
            f[j] += f[j - m[i]];//买
 
    cout << f[n];
    return 0;
}

例题2 . 货币系统：

信息学奥赛一本通T1273-货币系统 - C语言网 (dotcpp.com)

思路：

和上题一样，有n个物品，每个物品无限个，有价值和体积属性，求恰好组成体积为 m 的方案数有多少；

f[i][j] 表示方案数；

f[i][j] 等于选当前货币和不选当前货币的方案数之和。

AC代码如下：

//二维
#include
using namespace std;
 
const int N = 3010, M = 20;
long long f[M][N];
int n, m;//货币种类和目标值
 
int main() {
    cin >> n >> m;
 
    int k;
    f[0][0] = 1;//注意要初始化
    for (int i = 1; i <= n; i++) {
        cin >> k;
        for (int j = 0; j <= m; j++) {
            f[i][j] += f[i - 1][j];//不选
            if (j >= k)f[i][j] += f[i][j - k];//选
        }
    }
 
    cout << f[n][m];
 
    return 0;
}
 
//一维
 
 
#include
using namespace std;
 
const int N = 3010;
long long f[N];
int n, m;//货币种类和目标值
 
int main() {
    cin >> n >> m;
 
    int k;
    f[0] = 1;//注意要初始化
    for (int i = 1; i <= n; i++) {
        cin >> k;
        for (int j = k; j <= m; j++)
            f[j] += f[j - k];
    }
 
    cout << f[m];
 
    return 0;
}