背包动态规划-完全背包

OJ: T1268

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

测试数据：
输入：
4 6
1 2
2 4
3 8
4 10
输出：16

代码实现如下：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-06-20 20:54:39
 * 最后修改: 2025-01-31 23:33:19
 * 文件描述: 这是一个完全背包问题的动态规划解法  O(N × m^2)
****************************************************************/

#include <iostream>
using namespace std;

const int MAXN=1000;
const int MAXV=100;
int dp[MAXN][MAXV];
int value[MAXV];
int weight[MAXN];

int main(){
    int n,m,ik[MAXN][MAXV];
   
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i]>>value[i];   
    for(int i=1;i<=n;i++){
        for (int j = 0; j <=m; j++){
            //k是指i商品被用的件数,当k为0时，也就代表不选i商品，相当于初始化dp[i][j]
            for (int k = 0; k*weight[i]<=j; k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);
            }
        }
    }
    cout<<dp[n][m];

    return 0;    
}

优化为二维DP：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-31 22:23:43
 * 最后修改: 2025-01-31 23:31:32
 * 文件描述: 这是一个完全背包问题的动态规划解法  O(N × V)
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int complete_knapsack(int N, int V, vector<int> & w, vector<int> &v){
    // dp[i][j] 表示前i个物品（物品1~i）、容量为j时的最大价值
    vector<vector<int> > dp(N+1,vector<int>(V+1,0));

    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            if(j<w[i]){dp[i][j]=dp[i-1][j];
            }else{
               // dp[i][j - w[i]] 表示在容量 j - w[i] 时已可能放入过当前物品，因此允许重复选取。
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    return dp[N][V];
}

int main(){
    int N=3;
    int V=5;
   // w和v数组改为1-based（索引0未使用）
    vector<int> w(N + 1, 0);  // w[1]=2, w[2]=3, w[3]=4
    vector<int> v(N + 1, 0);  // v[1]=3, v[2]=4, v[3]=5
    w[1] = 2; v[1] = 3;
    w[2] = 3; v[2] = 4;
    w[3] = 4; v[3] = 5;

    int result=complete_knapsack(N,V,w,v);
    cout<<"Maximum value:"<<result<<endl;
}

动态方程：dp[i][j] = max(dp[i-1][j], dp[i][j – weight[i]] + value[i])

dp[i][j] = max(
dp[i-1][j], // 不选物品i
dp[i][j - w[i]] + v[i] // 选至少一个物品i（依赖当前层已更新的状态）
)

当 j >= w[i] 时：
- dp[i][j - w[i]] 表示在容量 j - w[i] 下，允许已经选取过物品i后的最优解。
- 如果物品i的“单位重量价值”较高，则重复选取会带来更高的总价值。
关键条件触发：
- 当 dp[i][j - w[i]] + v[i] > dp[i-1][j] 时，说明在当前容量 j 下，至少选取一个物品i比完全不选更优。
- 这种情况常见于物品i的性价比（价值/重量）高于前i-1个物品的组合。

动态规划的直观意义

正序遍历容量：
完全背包中正序遍历 j 保证了在计算 dp[i][j] 时，dp[i][j - w[i]] 可能已经包含了当前物品i的多次选取结果。例如：
- 当计算 dp[i][4] 时，dp[i][2] 可能已经通过 dp[i][0] + v[i] = 3 更新过。
- 这种设计允许同一物品被多次选取。
与01背包的对比：
01背包中逆序遍历容量 j，且状态转移使用 dp[i-1][j - w[i]]，确保每个物品只能被选一次。完全背包的正序设计打破了这一限制。

也可以优化为一维动态数组：

for (int i = 1; i <= n; i++) {
    for (int j = weight[i]; j <= m; j++) { // 正序遍历
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

背包动态规划-完全背包

动态规划的直观意义