C语言实现0-1背包问题（详细实现）并且动态实现0-1背包问题
目录
解释：
什么是0-1背包：
实例讲解
代码思想：
步骤实现详解：
代码实现：
头文件代码：
.c实现代码：
测试文件代码实现：
最后文件的效果：
解释：
此C语言实现的代码依旧是依据我用java写代码的那个0-1背包问题思路去实现唯一不同的就是C语言不能直接定义二维动态数组 需要我们去malloc一下，比较费劲，同时不要忘记最后释放内存以免造成内存泄漏。这两个博客都可以参考：发现不足可以评论修正我乐意接收善意的批评。
这里一维动态数组的创建就不详细说了很容易理解；
那么说说二维动态数组创建的解释把：
主要代码实现：
int** m = (int**)malloc(sizeof(int*) * n);
for (int i = 0; i < n; i++)
{
m[i] = (int*)malloc(sizeof(int) * (c + 1));
}这里malloc二维数组 先malloc二维；就是 int** m = (int**)malloc(sizeof(int*) * n); 这里需要注意" (int**)malloc(sizeof(int*) * n);当中的 "sizeof(int*)""这个需要特别注意sizeof进行计算的是int*，这位下一步进行操作打下基础。它相当于创建了二维数组的行，而多少列创建则有这个代码实现：
for (int i = 0; i < n; i++)
{
m[i] = (int*)malloc(sizeof(int) * (c + 1));
}这一步确定了二维动态数组需要多少列。这样我们动态二维数组创建成功；
但是为了不造成内存泄漏，我们要记得最后去释放掉；二维数组的释放代码实现是这样的：
for (int i = 0; i < n; i++)
{
free(m[i]);
}
free(m);
什么是0-1背包：
背包问题通俗的说，就是假如你面前有5块金块速分别为a, b, c, d, e，每块金块的重量不同，并且每块金块所带来的价值也不同（注意：这里金块的重量的价值没有特定关系），目前我们有一个背包，只有固定的容量，要解决的问题就是在一定容量的背包面前装哪几块金块才能获取到最大的价值，对于每块金块我们只有拿或者不拿这两种选择，拿为1不拿为0，因此叫做0-1背包问题。下面我们给出思想，以及步骤
实例讲解
假设a, b, c, d, e五块金块的重量分别为1， 4， 2， 5， 2，价值分别为1， 6， 5，3， 1 ，我们目前的背包可以装重量为10的物品，怎么装才能使得获取的价值最大？
我们的思想很简单，就是我们把它们装到背包中，带出去让他属于自己，但是如果盲目的去装，不知道他们的价值，你装到背包里面的没有别人装到背包里面的价值高，那么你就等于这次你吃亏了，没有动脑筋，只顾着去装满背包了，那么我们动态规划一下，它却能帮助我们取得最大值。那么我们是不是有必要去规划一下。
实例规划：
背包容量c:10
w(重量): 1， 4， 2， 5， 2
v(价值): 1， 6， 5，3， 1
上面的数组数字是物品的重量和下面是其对应的价值，那么我们想要是背包利用空间充足利用同时保持最后结果为最大价值，那么由上面我们可以很容易的相处最优解，就是最大价值：13背包里面装：1 4 2 2
对应价值 1 6 5 1 输出最大价值为：1+6+5+1=13；
那么物品种类少我们能看出来，如果物品多了我们就看不出来了背包容量c:20
比如： w（重量）： 1 5 15 13 4 8 9 6 3 1 2
v （价值）： 5 9 10 8 13 11 15 2 3 7 9
这样一来上面的数组数字在想要很快的找出最优解，最大价值，就很难很快得出结论，那么这样就可以把它动态规划实现在计算机上让它来帮助我们找出最大价值。那么下面我们开始进行计算机代码实现。
代码思想：
主要执行公式：动态规划算法
步骤实现详解：
我们以这个数组例子作为讲解：n(物品种类)； c(背包容量)； w(每个物品的的重量)；v(每个物品对应的价值（w1对应v1）);
实现：
第一行根据上面公式得公式：
根据代码：
void knapsaack(int v[], int w[], int c, int** m, int n)
{
n = n - 1;
int min = Min(w[n] - 1, c);
for (int i = 0; i <= min; i++)
{
m[n][i] = 0;
}
for (int i = w[n]; i <= c; i++)
{
m[n][i] = v[n];
}for (int i = n - 1; i >= 0; i--)
{
min = Min(w[i] - 1, c);
for (int j = 0; j <= min; j++)
{
m[i][j] = m[i + 1][j];
}
for (int j = w[i]; j <= c; j++)
{
m[i][j] = Max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
}}
}
我标记红色的是实现第一行填入的数字；
可以把表格填入：
剩余行根据公式：
根据代码可填入：
void knapsaack(int v[], int w[], int c, int** m, int n)
{
n = n - 1;
int min = Min(w[n] - 1, c);
for (int i = 0; i <= min; i++)
{
m[n][i] = 0;
}
for (int i = w[n]; i <= c; i++)
{
m[n][i] = v[n];
}for (int i = n - 1; i >= 0; i--)
{
min = Min(w[i] - 1, c);
for (int j = 0; j <= min; j++)
{
m[i][j] = m[i + 1][j];
}
for (int j = w[i]; j <= c; j++)
{
m[i][j] = Max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
}}
}
这些标记红色的实现下面没有填入二维数组的数字。
结论：
那么可知：m[0][c]就是我们想要的结果，即是上表的m[0][10]；就是0-1背包的最优解；能存放的最大值。
代码实现：
头文件代码：
#pragma once#include
#include
#includevoid knapsaack(int v[], int w[], int c, int** m);
int Min(int a, int b);
int Max(int a, int b); .c实现代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include"knapsack.h"int Min(int a, int b)
{if (a > b){return b;}else{return a;}}int Max(int a, int b)
{if (a > b){return a;}else{return b;}
}void knapsaack(int v[], int w[], int c, int** m, int n)
{n = n - 1;int min = Min(w[n] - 1, c);for (int i = 0; i <= min; i++){m[n][i] = 0;}for (int i = w[n]; i <= c; i++){m[n][i] = v[n];}for (int i = n - 1; i >= 0; i--){min = Min(w[i] - 1, c);for (int j = 0; j <= min; j++){m[i][j] = m[i + 1][j];}for (int j = w[i]; j <= c; j++){m[i][j] = Max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);}}}测试文件代码实现：
#define _CRT_SECURE_NO_WARNINGS 1#include"knapsack.h"/*** 动态规划实现0-1背包在固定容量c的情况下获得最大价值问题，输出可容纳的最大价值，输入物品种类、背包容量、物品重量和价值，输出最大价值。**** 格式要求可参考如下：** 输入：** 请输入物品种类n，并按Enter换行:5** 请输入背包容量c，并按Enter换行:10** 请输入n个物品的重量，中间以英文逗号隔开，按Enter结束：1,4,2,5,2** 请输入n个物品的价值，中间以英文逗号隔开，并按Enter结束： 1,6,5,3,1** 输出：13*/int main()
{int n = 0, c = 0;printf("请输入物品种类的个数n:>");scanf("%d", &n);printf("请输入背包容量c:>");scanf("%d", &c);printf("请输入n个物品的重量，中间以英文逗号隔开，按Enter结束：>");int* w = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){scanf("%d,", &w[i]);}printf("请输入n个物品的价值，中间以英文逗号隔开，并按Enter结束：>");int* v = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){scanf("%d,", &v[i]);}int** m = (int**)malloc(sizeof(int*) * n);for (int i = 0; i < n; i++){m[i] = (int*)malloc(sizeof(int) * (c + 1));}knapsaack(v, w, c, m, n);printf("输出最大的价值为:>%d", m[0][c]);free(w);w = NULL;free(v);v = NULL;for (int i = 0; i < n; i++){free(m[i]);}free(m);return 0;
}
最后文件的效果：
大概就是这样的创建和分布。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！