资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

数据结构与算法之背包问题

创作时间:

作者:

@小白创作中心

数据结构与算法之背包问题

引用

CSDN

https://m.blog.csdn.net/weixin_47225948/article/details/133066311

背包问题是一个经典的优化问题，也是计算机科学中的经典问题之一。它的核心思想是，在有限的容量下，如何选择物品，使得其总价值最大。

具体来说，背包问题可以分为0-1背包问题和分数背包问题两种类型。

0-1背包问题指的是在有限的容量下，每个物品只能选取一次。因此，该问题可以抽象为一个二维数组，其中行表示不同的物品，列表示不同的容量，数组元素表示在当前容量下，选择第i个物品能够获得的最大价值。

分数背包问题指的是在有限的容量下，每个物品可以选取一部分。因此，该问题可以抽象为一个排序数组，其中元素表示选取不同物品的单位价值，然后按照单位价值从大到小进行排序。接着按照排序后的顺序，依次选取物品，直到达到背包的容量上限。

在实际应用中，背包问题常常被用于资源分配、货物装载、投资决策、排产计划等领域，是一个非常有用的工具。

C语言实现

背包问题是一道经典的动态规划问题，其基本思路是：设f[i][j]表示前i个物品放入一个容量为j的背包可以获得的最大价值，其中第i个物品的体积为w[i]，价值为v[i]。则对于第i个物品，我们有两种选择：放入背包或不放入背包，根据这个思路，我们可以得到如下的状态转移方程：

f[i][j] = max{ f[i-1][j], f[i-1][j-w[i]] + v[i] }

其中，f[i-1][j]表示不放入第i个物品时的最大价值，f[i-1][j-w[i]]+v[i]表示放入第i个物品时的最大价值。

以下是C语言的背包问题代码实现和详解：

#include <stdio.h>
#include <string.h>

// 物品数量、背包容量
#define N 5
#define V 10

// 物品的体积和价值，注意第0个元素不使用
int w[N+1] = {0,2,3,5,7,9};
int v[N+1] = {0,3,4,7,8,10};

// 存储最大价值的数组
int f[N+1][V+1];

int main()
{
    memset(f, 0, sizeof(f)); // 将f数组全部初始化为0

    // 计算最大价值
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < w[i]) {
                f[i][j] = f[i-1][j];
            } else {
                f[i][j] = f[i-1][j] > (f[i-1][j-w[i]]+v[i]) ? f[i-1][j] : f[i-1][j-w[i]]+v[i];
            }
        }
    }

    // 打印最大价值
    printf("最大价值为：%d\n", f[N][V]);
    return 0;
}

代码说明：

首先定义了物品数量和背包容量的常量，这里设为5和10。因此，我们有5个物品，背包容量为10。
定义物品的体积和价值数组，注意第0个元素不使用。例如，第一个物品的体积为2，价值为3。
定义存储最大价值的二维数组f，其中f[i][j]表示前i个物品放入容量为j的背包时的最大价值。
初始化f数组为0。
使用两个for循环遍历所有i和j的取值，计算f[i][j]的最大价值。根据上述状态转移方程，当背包容量小于物品体积时，无法放入该物品，此时f[i][j]的最大价值与f[i-1][j]相同；否则，f[i][j]的最大价值为f[i-1][j]和f[i-1][j-w[i]]+v[i]中的较大值。其中，f[i-1][j]表示不放入第i个物品时的最大价值，f[i-1][j-w[i]]+v[i]表示放入第i个物品时的最大价值。
最后输出最大价值。

总之，该代码实现了背包问题的求解，其时间复杂度为O(NV)，空间复杂度为O(NV)。

C++实现

背包问题是一种经典的动态规划问题，其主要思想是：在有限的背包容量下，选择一定数量的物品，使得所选择的物品价值之和最大化。

下面以 0/1 背包问题为例，介绍 C++ 实现和算法思路。

算法思路：
0/1 背包问题指的是，在背包容量固定的情况下，每个物品要么选择，要么不选，即每个物品只能使用一次。因此，我们考虑使用动态规划的方法来解决这个问题。

设 f[i][j] 表示在前 i 个物品中选择若干个物品装入容量为 j 的背包中，所能获得的最大价值。则有以下状态转移方程：

当第 i 个物品体积大于 j 时，f[i][j] = f[i-1][j]
当第 i 个物品体积小于等于 j 时，f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i])

其中，v[i] 表示第 i 个物品的体积，w[i] 表示第 i 个物品的价值。

代码实现：
下面是 0/1 背包问题的 C++ 实现代码。其中，n 表示物品数量，m 表示背包容量，w 和 v 分别表示每个物品的体积和价值。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int w[n+1],v[n+1];
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    int f[n+1][m+1];
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(w[i]>j){
                f[i][j]=f[i-1][j];
            }
            else{
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

代码解释：

首先输入物品数量 n 和背包容量 m。
接着输入每个物品的体积和价值。
定义动态规划数组 f[n+1][m+1]，并将其初始值全部赋为 0。
使用双重循环，遍历每个物品和每个背包容量，根据状态转移方程更新 f[i][j]。
输出 f[n][m]，即为所求的最大价值。

总结：
0/1 背包问题是一种经典的动态规划问题，其算法思路简单易懂。使用动态规划可以有效地解决背包问题，代码实现也比较简单。在使用动态规划解决问题时，需要注意合理地定义状态，以及正确地编写状态转移方程。

Java实现

背包问题是一种经典的动态规划问题。具体来说，给定一组物品，每种物品都有一个重量和一个价值，需要选择一些物品放入一个背包中，使得背包能够承受的重量最大，并且选出的物品具有最大的总价值。

Java 实现背包问题的代码如下：

public class Knapsack {
    static int max(int a, int b) {
        return (a > b) ? a : b;
    }
    static int knapSack(int W, int wt[], int val[], int n) {
        int i, w;
        int[][] K = new int[n + 1][W + 1];
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    K[i][w] = 0;
                } else if (wt[i - 1] <= w) {
                    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
                } else {
                    K[i][w] = K[i - 1][w];
                }
            }
        }
        return K[n][W];
    }
    public static void main(String args[]) {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}

该代码实现了动态规划的思想，使用了二维数组 K 来记录每个子问题的最优解，并逐步构建出最终问题的最优解。具体来说，代码中的 K[i][w] 表示在背包容量为 w 时前 i 个物品的最大价值，其中 i 取值从 0 到 n，w 取值从 0 到 W。对于每个子问题，其状态转移方程为：

if (wt[i - 1] <= w) {
    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
} else {
    K[i][w] = K[i - 1][w];
}

其中，如果第 i 个物品的重量小于等于当前背包容量 w，则可以将其放入背包中，此时可以获得 val[i-1] 的收益，但需要考虑前 i-1 个物品的最大收益，即 K[i-1][w-wt[i-1]]。如果第 i 个物品的重量大于当前背包容量 w，则无法将其放入背包，此时背包的最大收益为前 i-1 个物品的最大收益，即 K[i-1][w]。