动态规划：01 背包问题详解 | 极客日志

C算法

动态规划：01 背包问题详解

动态规划解决 01 背包问题，核心在于状态定义与转移方程。文章详细对比了二维数组与一维滚动数组的实现差异，解释了为何一维数组需逆序遍历以避免重复选择。通过携带研究材料、砝码称重、分组砝码组合及装箱问题四个实例，演示了不同场景下的 DP 建模方法。包括如何处理物品价值与体积相等的情况，以及天平称重中砝码可放两侧的逻辑推导。最终提供完整的 C 语言代码示例，涵盖内存分配、输入输出及空间优化技巧。

独立开发者发布于 2026/3/15更新于 2026/4/183 浏览

01 背包问题

一、二维数组实现 01 背包

包括物品和背包，但每个物品的数量只有一个，所以只需要考虑选一个和不选两种情况。

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

在下面的讲解中，举一个例子：

背包最大重量为 4。

物品为：

	重量	价值

// 固定物品 i，计算它在所有容量 j 下的 dp 值
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= bagweight; j++) {
        // ...
    }
}

// 固定容量 j，计算所有物品在这个容量下的 dp 值
for (int j = 0; j <= bagweight; j++) {
    for (int i = 1; i <= n; i++) {
        // ...
    }
}

6 1 2 2 3 1 5 2 2 3 1 5 4 3

#include <stdio.h>
#include <stdlib.h>

// 获取最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, bagweight;
    // bagweight 代表行李箱空间
    scanf("%d %d", &n, &bagweight);
    
    // 动态分配数组
    int *weight = (int *)malloc(n * sizeof(int)); // 存储每件物品所占空间
    int *value = (int *)malloc(n * sizeof(int)); // 存储每件物品价值
    
    for(int i = 0; i < n; ++i) {
        scanf("%d", &weight[i]);
    }
    for(int j = 0; j < n; ++j) {
        scanf("%d", &value[j]);
    }
    
    // 动态分配二维 dp 数组
    // dp[i][j] 代表行李箱空间为 j 的情况下，从下标为 [0, i] 的物品里面任意取，能达到的最大价值
    int **dp = (int **)malloc(n * sizeof(int *));
    for(int i = 0; i < n; i++) {
        dp[i] = (int *)malloc((bagweight + 1) * sizeof(int));
        // 初始化为 0
        for(int j = 0; j <= bagweight; ++j) {
            dp[i][j] = 0;
        }
    }
    
    // 初始化第一行
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }
    
    // 动态规划计算
    for(int i = 1; i < n; i++) {
        // 遍历物品
        for(int j = 0; j <= bagweight; j++) {
            // 遍历行李箱容量
            if (j < weight[i]) {
                dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品，那么就继承 dp[i - 1][j] 的值
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    
    printf("%d\n", dp[n - 1][bagweight]);
    
    // 释放动态分配的内存
    for(int i = 0; i < n; ++i) {
        free(dp[i]);
    }
    free(dp);
    free(weight);
    free(value);
    
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 用于 abs 函数
int n, ans, sum, w[101], dp[101][100001];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = sum; j > 0; j--) {
            // 注意：这里 j 从 sum 递减到 1
            if (j == w[i]) {
                dp[i][j] = 1;
            } else if (dp[i-1][j]) {
                dp[i][j] = 1;
            } else if (dp[i-1][j + w[i]]) {
                dp[i][j] = 1;
            } else if (dp[i-1][abs(j - w[i])]) {
                dp[i][j] = 1;
            }
        }
    }
    
    for (int i = 1; i <= sum; i++) {
        if (dp[n][i]) {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

#include<stdio.h>
int main() {
    int a[4];
    int weight,i,j;
    for(i=0;i<4;i++){ 
        scanf("%d",&a[i]); 
    }
    scanf("%d",&weight);
    int dp[5][1001]={0};
    int values[4] = {1, 2, 5, 10};
    dp[0][0]=1;
    int k;
    for(i=1;i<=4;i++){
        for(j=0;j<=weight;j++){
            dp[i][j]=dp[i-1][j];
            for(k=1;k<=a[i-1];k++){
                if(j >= k * values[i-1]){
                    dp[i][j]=dp[i][j]+dp[i-1][j-k*values[i-1]];
                }
            }
        }
    }
    if(dp[4][weight]>0){ 
        printf("%d",dp[4][weight]); 
    }else{
        printf("cannot compose"); 
    }
    return 0;
}

c
for(i=1;i<=4;i++){
    for(j=0;j<=weight;j++){
        dp[i][j]=dp[i-1][j];
        for(k=1;k<=a[i-1];k++){//遍历的是每组的砝码数量
            if(j >= k * values[i-1]){
                dp[i][j]=dp[i][j]+dp[i-1][j-k*values[i-1]];//到这里还是和'摆花'问题几乎一样，但不要忘了因为二者小小的区别造成的 k*values[i-1]。
            }
        }
    }
}

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}

int main() {
    int q;
    scanf("%d",&q);
    int n;
    scanf("%d",&n);
    int i,j;
    int* v=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
    }
    
    int** dp=(int **)malloc((n+1)*sizeof(int*));
    for(i=0;i<=n;i++){
        dp[i]=(int *)malloc((q+1)*sizeof(int));
        for(j=0;j<=q;j++){
            dp[i][j]=0;
        }
    }
    
    for(i=1;i<=n;i++){
        for(j=0;j<=q;j++){
            if(j<v[i-1]){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+v[i-1]);
            }
        }
    }
    
    printf("%d\n",q-dp[n][q]);
    for(i=0;i<=n;i++){
        free(dp[i]);
    }
    free(dp);
    free(v);
    return 0;
}

// 装箱代码
for(i=0;i<=n;i++){ // 1.区别
    dp[i]=(int *)malloc((q+1)*sizeof(int));
    for(j=0;j<=q;j++){
        dp[i][j]=0;
    }
}
// 2.区别
for(i=1;i<=n;i++){
    for(j=0;j<=q;j++){
        if(j<v[i-1]){ // 3.区别
            dp[i][j]=dp[i-1][j];
        }else{
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+v[i-1]);
        }
    }
}

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}

int main() {
    int q; // 行李箱空间
    scanf("%d",&q);
    int n; // 物品数量
    scanf("%d",&n);
    int i,j;
    int* v=(int *)malloc(n*sizeof(int)); // 物品体积
    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
    }
    
    // dp[i][j] 表示前 i+1 个物品（索引 0 到 i）在容量 j 下的最大体积
    int** dp=(int **)malloc(n*sizeof(int*)); // 只需要 n 行，因为 i 从 0 到 n-1
    for(i=0;i<n;i++){
        dp[i]=(int *)malloc((q+1)*sizeof(int));
        for(j=0;j<=q;j++){
            dp[i][j]=0; // 初始化
        }
    }
    
    // 初始化第一行（i=0，即只考虑第 1 个物品，索引 0）
    for(j=v[0]; j<=q; j++){
        dp[0][j] = v[0]; // 容量足够时，可以放入第一个物品
    }
    
    // 注意：当 j<v[0] 时，dp[0][j] 已经是 0（初始化时设置）
    
    // 动态规划
    for(i=1; i<n; i++){
        // i 从 1 到 n-1，表示考虑物品 0 到 i
        for(j=0; j<=q; j++){
            // j 从 0 到 q
            if(j < v[i]){ // 当前容量小于第 i+1 个物品的体积
                dp[i][j] = dp[i-1][j]; // 不选当前物品
            }else{ // 选或不选当前物品，取最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + v[i]);
            }
        }
    }
    
    // 输出最小剩余空间：总容量 - 最大可装入体积
    // dp[n-1][q] 表示考虑所有 n 个物品时能装入的最大体积
    printf("%d\n", q - dp[n-1][q]);
    
    // 释放内存
    for(i=0;i<n;i++){
        free(dp[i]);
    }
    free(dp);
    free(v);
    return 0;
}

	重量	价值
物品 0	1	15
物品 1	3	20
物品 2	4	30

容量	0	1	2	3	4
价值	0	15	15	15	15

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int M, N; // 读取 M 和 N
    scanf("%d %d", &M, &N);
    
    // 动态分配数组
    int *costs = (int*)malloc(M * sizeof(int));
    int *values = (int*)malloc(M * sizeof(int));
    int *dp = (int*)malloc((N + 1) * sizeof(int));
    
    if (costs == NULL || values == NULL || dp == NULL) {
        return 1;
    }
    
    // 读取成本
    for (int i = 0; i < M; i++) {
        scanf("%d", &costs[i]);
    }
    
    // 读取价值
    for (int j = 0; j < M; j++) {
        scanf("%d", &values[j]);
    }
    
    // 初始化 dp 数组为 0
    for (int i = 0; i <= N; i++) {
        dp[i] = 0;
    }
    
    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; j--) {
            // 考虑当前研究材料选择和不选择的情况，选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }
    
    // 输出 dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
    printf("%d\n", dp[N]);
    
    // 释放内存
    free(costs);
    free(values);
    free(dp);
    
    return 0;
}

输入 24 6 8 3 12 7 9 7
输出 0
说明/提示 对于 100% 数据，满足 0<n≤30，1≤V≤20000。

#include <stdio.h>
#include <stdlib.h>

// 定义 max 函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int v;
    scanf("%d", &v); // 分配 dp 数组，需要 v+1 个元素（0 到 v）
    int *dp = (int *)malloc((v + 1) * sizeof(int));
    
    int n;
    scanf("%d", &n);
    
    // 分配 a 数组
    int *a = (int *)malloc(n * sizeof(int));
    int i, j;
    
    // 读取数组元素
    for(i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 初始化 dp 数组，容量为 i 的背包最大价值为 0
    for(i = 0; i <= v; i++) {
        dp[i] = 0;
    }
    
    // 0-1 背包动态规划
    for(i = 0; i < n; i++) {
        for(j = v; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        }
    }
    
    // 输出结果
    if(dp[v] == v) {
        printf("0\n");
    } else if(dp[v] < v) {
        printf("%d\n", (v - dp[v]));
    }
    
    // 释放内存
    free(dp);
    free(a);
    
    return 0;
}

动态规划：01 背包问题详解

01 背包问题

一、二维数组实现 01 背包

1. 确定 dp 数组以及下标的含义

2. 确定递推公式

3. dp 数组初始化

4. 确定遍历顺序

例题一：携带研究材料

题目描述

输入描述

输出描述

输入示例

输出示例

提示信息

代码展示

例题二：砝码称重

题目描述

输入格式

输出格式

输入

输出

说明/提示

代码实现：

（2）砝码来组合 (分组背包)

题目描述

输入

输出

代码实现：

例题三：装箱问题

题目描述

输入格式

输出格式

输入

输出

说明/提示

代码实现：

二、滚动数组 (一维) 实现 01 背包

1. 确定 dp 数组定义及下标含义

2. 确定递推公式

3. 如何初始化

4. 一维 dp 数组遍历顺序

三、例题：装箱问题（一维优化）

题目描述

输入格式

输出格式

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具