C语言0-1背包问题
为什么代码编译的时候没有报错但运行的时候只能运行一半
#include
#define mn 50
int min(int a,int b)
{
int min;
if(ab) max=a;
return 0;
}
void Knapsack(int *v, int *w, int c, int n, int (*m)[mn])
//v[]物品的价值，w[]物品的重量，c背包容量，n物品数量，m[i][j]是背包容量为j，可选择物品为i,i+1....n的最优值
{
int j,i;
//先判断第n个物品能不能装入背包
int jMax = min(w[n]-1,c);
//当0<=j<=w[n]时，m(n,j)=0
for(j=0; j<=jMax;j++) m[n][j]=0;
//当j>=w[n]时，m(n,j)=v[n]
for(j=w[n]; j<=c; j++) m[n][j] = v[n];
//再从n-1往前开始判断第n个物品到第i个物品能不能装下
for(i=n-1; i>1; i--)
{ jMax = min(w[i]-1,c);
for(j=0; j<=jMax; j++)//背包剩余容量j<=jMax1][j];//无法装入第i个物品
for(j=w[i]; j<=c; j++)
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
//判断第n个到第1个物品能不能装下
m[1][c] = m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
//x[]数组: 值为0表示不装入背包，值为1表示装入背包
void Traceback(int (*m)[mn], int *w, int c, int n, int *x)
{
int i;
for(i=1; i1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}
int main()
{
int n,c,i;
printf("请输入物品的数量n=");
scanf("%d",&n);
printf("请输入背包的容量c=");
scanf("%d",&c);
int w[100];
printf("请依次输入各物品的重量:");
for(i=1;i<=n;i++)
scanf("%d",w[i]);
int v[100];
printf("请依次输入各物品的价值:");
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
int m[mn][mn];
int x[100];
int mw=0;
int mv=0;
//进行查找与回溯
Knapsack(v,w,c,n,m);
Traceback(m,w,c,n,x);
//输出最优序列和最优重量与最优值
printf("最优装载序列为：\n");
for(i=1;i<=n;i++)
{
printf("&d",x[i]);
mw=mw+x[i]*w[i];
mv=mv+x[i]*v[i];
}
printf("最大重量为：%d\n最大价值为：%d\n",mw,mv);
return 0;
}
运行结果
基于new Bing的回答：
在代码中，有一个max函数的返回值是0，应该改为返回max。修改后的代码如下：
#include <stdio.h>
#define mn 50
int min(int a,int b)
{
int min;
if(a<b) min=a;
return min;
}
int max(int a,int b)
{
int max;
if(a>b) max=a;
else max=b; //修改这里，返回max值
return max;
}
void Knapsack(int *v, int *w, int c, int n, int (*m)[mn])
//v[]物品的价值，w[]物品的重量，c背包容量，n物品数量，m[i][j]是背包容量为j，可选择物品为i,i+1....n的最优值
{
int j,i;
//先判断第n个物品能不能装入背包
int jMax = min(w[n]-1,c);
//当0<=j<=w[n]时，m(n,j)=0
for(j=0; j<=jMax;j++) m[n][j]=0;
//当j>=w[n]时，m(n,j)=v[n]
for(j=w[n]; j<=c; j++) m[n][j] = v[n];
//再从n-1往前开始判断第n个物品到第i个物品能不能装下
for(i=n-1; i>1; i--)
{
jMax = min(w[i]-1,c);
for(j=0; j<=jMax; j++)//背包剩余容量j<=jMax<c
m[i][j] = m[i+1][j];//无法装入第i个物品
for(j=w[i]; j<=c; j++)
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
//判断第n个到第1个物品能不能装下
m[1][c] = m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
//x[]数组: 值为0表示不装入背包，值为1表示装入背包
void Traceback(int (*m)[mn], int *w, int c, int n, int *x)
{
int i;
for(i=1; i<n; i++)
{
if(m[i][c] == m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}
int main()
{
int n,c,i;
printf("请输入物品的数量n=");
scanf("%d",&n);
printf("请输入背包的容量c=");
scanf("%d",&c);
int w[100];
printf("请依次输入各物品的重量:");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
int v[100];
printf("请依次输入各物品的价值:");
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
int m[mn][mn];
int x[100];
int mw=0;
int mv=0;
//进行查找与回溯
Knapsack(v,w,c,n,m);
Traceback(m,w,c,n,x);
//输出最优序列和最优重量与最优值
printf("最优装载序列为：\n");
for(i=1;i<=n;i++)
{
printf("%d",x[i]);
mw=mw+x[i]*w[i];
mv=mv+x[i]*v[i];
}
printf("\n最大重量为：%d\n最大价值为：%d\n",mw,mv);
return 0;
}
int min(int a,int b)
{
int min;
if(a<b) min=a;
return min;
}
int max(int a,int b)
{
int max;
if(a>b) max=a; ？？？？？？
return 0;？？？？？？
你这两段代码在干嘛？？？？
两个取最小、最大值的函数修改如下，供参考：
int min(int a,int b)
{
int min;
if(a<b)
min=a;
else //修改
min=b; //修改
return min;
}
int max(int a,int b)
{
int max;
if(a>b)
max=a;
else //修改
max=b; //修改
return max;//return 0; 修改
}
以下内容部分参考ChatGPT模型：
问题分析：
1.代码中存在语法错误，如“<”、“>”应该改为“<”、“>”；
2.代码中的max函数始终返回0，应该返回max值；
3.在输入物品重量和价值时，数组下标应该从0开始而不是1；
4.在输出最优装载序列时，printf语句中缺少格式控制符。
解决思路：
1.修改语法错误，将“<”、“>”改为“<”、“>”；
2.修改max函数，返回max值；
3.修改数组下标，从0开始而不是1；
4.修改输出最优装载序列的printf语句，添加缺少的格式控制符。
代码实现如下：
如果我的建议对您有帮助、请点击采纳、祝您生活愉快
- 你可以看下这个问题的回答https://ask.csdn.net/questions/7481025
- 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：【数据结构从0到1】总结篇：C语言实现初阶数据结构
- 同时，你还可以查看手册：c语言-内存模型与数据竞争 中的内容
- 除此之外, 这篇博客: 动态规划法解决0-1背包问题中的 使用C语言实现的代码如下所示 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> /* 动态规划法解决0-1背包问题(使用递推公式进行数据生成) */ /* 定义背包的属性 */ int package_total_contain; //背包的容量 int package_max_value; //在不超过背包容量的前提下，放入背包中的物品实现的最大价值 /* 定义物品的属性 */ int goods_total_num; //总的物品的数量 int *pArrayGoodsWeight; //定义一个指针指向存放物品重量的数组 int *pArrayGoodsValue; //定义一个指针指向存放物品价值的数组 int *pArrayGoodsCount; //定义指针指向存放物品是否被选中的数组，选中就置为1，未选中就置为0，与物品一一对应,以此得出选取物品是哪些 /* 函数的声明 */ void Init(); int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount); void DisPlay(int maxValue); int main() { Init(); int maxValue = GetMaxValue(goods_total_num, package_total_contain, pArrayGoodsWeight, pArrayGoodsValue, pArrayGoodsCount); //maxValue的值为-1时，表示用户的输入非法，程序直接结束 if (maxValue == -1) { system("pause"); return 0; } DisPlay(maxValue); system("pause"); return 0; } /* 初始化函数，进行基本数据(背包的容量、物品的数量以及各个物品的重量与价值)的初始化 */ void Init() { printf("请输入背包的的最大容量："); scanf("%d", &package_total_contain); printf("请输入物品的数量："); scanf("%d", &goods_total_num); //背包的重量有0的这一列，所以分配的空间要加1 pArrayGoodsWeight = (int *)malloc(sizeof (int) * (goods_total_num + 1)); for (int i = 1; i <= goods_total_num; i++) { printf("请输入第%d个物品的重量：",i); scanf("%d", pArrayGoodsWeight + i); } printf("\n"); //物品的编号有0的这一行，所以分配的空间要加1 pArrayGoodsValue = (int *)malloc(sizeof (int) * (goods_total_num + 1)); for (int i = 1; i <= goods_total_num; i++) { printf("请输入第%d个物品的价值：",i); scanf("%d", pArrayGoodsValue + i); } //该数组与物品编号一一对应，选中就置为1，未选中就置为0，刚开始时全部初始化为0，也是从1开始存储的 pArrayGoodsCount = (int *)malloc(sizeof(int) * (goods_total_num + 1)); for (int i = 1; i <= goods_total_num; i++) { pArrayGoodsCount[i] = 0; } /* 进行用户当前基本输入数据的显示，方便用户的对比 */ printf("\t\t\t\t您输入的数据如下图所示\n\n"); printf("\t\t 物品序号\t\t 物品重量\t\t 物品价值\n"); for (int i = 1; i <= goods_total_num; i++) { printf("\t\t%8d\t\t%8d\t\t%8d\n", i, pArrayGoodsWeight[i], pArrayGoodsValue[i]); } printf("\n"); } /* 该函数实现生成最大价值表以及得出实现的最大价值和物品选择序列 @param goods_total_num 物品的总数量 @param package_total_contain 背包的最大容量 @param pArrayGoodsWeight 指向保存物品重量数组的首地址的指针变量 @param pArrayGoodsValue 指向保存物品价值数组的首地址的指针变量 @param pArrayGoodsCount 指向保存物品是否被选中数组的首地址的指针变量 **/ int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount) { //表示用户输入了背包容量或物品数量非法时，直接返回-1，将不执行生成最大价值表的程序 if (goods_total_num <= 0 || package_total_contain <= 0) { return -1; } //表格的行数等于物品的数量，每个物品对应一行数据，由于有一行全为0，所以要加上1 int row_num = goods_total_num + 1; //表格的列是按照背包重量从1开始进行递增，由于有背包重量是0的那一列，所以列数等于背包重量加1 int col_num = package_total_contain + 1; //创建一个value指针变量，存放行的指针数组信息 int ** value = (int **)malloc(sizeof (int *)); //创建行数组，并将首地址发送给value指针 value = (int **)malloc(sizeof(int *) * row_num); //创建列数组，并将首地址发送给行指针数组 for (int i = 0; i < col_num; i++) { value[i] = (int *)malloc(sizeof(int) * col_num); } //进行初始化操作，初始化第0行,设置该行数值为0 for (int i = 0; i < col_num; i++) { value[0][i] = 0; } //进行初始化操作，初始化第0列,设置该行数值为0 for (int i = 0; i < row_num; i++) { value[i][0] = 0; } //进行计算,算出每一行每一列的最大价值,i表示物品编号，j表示背包容量 for (int i = 1; i < row_num; i++) { for (int j = 1; j < col_num; j++) { //如果是该中情况，表明此时背包已经装不下了，该件物品将不会放入背包 value[i][j] = value[i - 1][j]; //如果物品能装入背包，此时的最大价值是该temp值 int tempValue = value[i - 1][j - pArrayGoodsWeight[i]] + pArrayGoodsValue[i]; //当物品能够放入背包中，并且放入的价值大于不放入的价值时，改变此时的最大价值 if (pArrayGoodsWeight[i] <= j && tempValue > value[i][j]) { value[i][j] = tempValue; } } } //最大价值表的列的下标最大值是col_num - 1 int j = col_num - 1; /* 逆推法求出装入的物品,从最右下角开始往前推 */ for (int i = row_num - 1; i > 0; i--) { //如果后面的价值大于前一个，表示该物品被选进了背包 if (value[i][j] > value[i - 1][j]) { //设置该物品被选中，作为一种标记,设置其值为1，以便知道哪些被选中了 pArrayGoodsCount[i] = 1; //将该物品的重量从总的重量中减去 j -= pArrayGoodsWeight[i]; } } //记录最大的价值 int max_value = value[row_num - 1][col_num - 1]; printf("\n"); //输出一个换行符 printf("\t最大价值表如下图所示\n"); printf(" "); //输出3个空格使数据对齐 for (int i = 0; i < col_num; i++) { printf("%3d", i); //进行列标题的输出，表示背包的重量 } printf("\n"); //输出一个换行符 //进行当前每一个value[i][j]值的打印,行数等于物品数量加1，纵向数量等于背包最大容量加1 for (int i = 0; i <= goods_total_num; i++) { printf("%3d", i); for (int j = 0; j <= package_total_contain; j++) { printf("%3d", value[i][j]); } printf("\n"); //每输出一行进行一次换行操作 } printf("\n"); //输出一个换行符 return max_value; } /* 该函数实现最终结果的显示 */ void DisPlay(int maxValue) { printf("实现的最大价值是：%d\n", maxValue); printf("选取的物品序列是："); for (int i = 1; i <= goods_total_num; i++) { if (pArrayGoodsCount[i] == 1) { printf("%d ", i); } } printf("\n"); }- 您还可以看一下 尹成老师的C语言系列之 链表与相关操作课程中的 指针与结构体补充小节, 巩固相关知识点
在你的代码上修改好了，你看看可以不，运行结果如下：
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#define mn 50
int min(int a, int b)
{
if (a < b) {
return a;
}
else {
return b;
}
}
int max(int a, int b)
{
if (a > b) {
return a;
}
else {
return b;
}
}
void Knapsack(int *v, int *w, int c, int n, int(*m)[mn])
{
int j, i;
int jMax;
for (j = 0, jMax = min(w[n] - 1, c); j <= jMax; j++) {
m[n][j] = 0;
}
for (j = w[n]; j <= c; j++) {
m[n][j] = v[n];
}
for (i = n - 1; i >= 1; i--) {
jMax = min(w[i] - 1, c);
for (j = 0; j <= jMax; j++) {
m[i][j] = m[i + 1][j];
}
for (j = w[i]; j <= c; j++) {
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
}
}
}
void Traceback(int(*m)[mn], int *w, int c, int n, int *x)
{
int i;
for (i = 1; i < n; i++) {
x[i] = (m[i + 1][c - w[i]] + w[i] <= c) ? 1 : 0;
c -= x[i] * w[i];
}
x[n] = (m[n][c] != 0);
}
int main() {
int n, c, i;
printf("请输入物品的数量n=");
scanf_s("%d", &n);
printf("请输入背包的容量c=");
scanf_s("%d", &c);
int w[100];
printf("请依次输入各物品的重量:");
for (i = 1; i <= n; i++) {
scanf_s("%d", &w[i]);
}
int v[100];
printf("请依次输入各物品的价值:");
for (i = 1; i <= n; i++) {
scanf_s("%d", &v[i]);
}
int m[mn][mn];
int x[100];
int mw = 0;
int mv = 0;
//进行查找与回溯
Knapsack(v, w, c, n, m);
Traceback(m, w, c, n, x);
//输出最优序列和最优重量与最优值
printf("最优装载序列为：\n");
for (i = 1; i <= n; i++) {
printf("%d ", x[i]);
mw = mw + x[i] * w[i];
mv = mv + x[i] * v[i];
}
printf("最大重量为：%d\n最大价值为：%d\n", mw, mv);
system("pause");
return 0;
}
运行结果如下：
