利用动态规划法求最大值,我用malloc函数动态创建规划表,当输入总预算小于等于8位数时都没问题,当输入9位数时就报错了。
我猜可能是因为数据太大数组放不下了?
还是什么原因,怎么解决哇
#include<stdio.h>
#include<malloc.h>
#include<algorithm>
#include <cassert>
#include <stdlib.h>
#define N 10010
int c; //测试用例个数
int n; //寿司种类
int m; //团队总预算
int a[N]; //存储物品的序号
int* value, * grade, * flag, ** p;
void knapsack();
int max(int a, int b);
void apply();
int main()
{
apply();
knapsack();
printf("%d", p[n][m]);
//释放
for (int i = 0; i < n+1; i++)
free(p[i]);
free(p);
free(value);
free(grade);
return 0;
}
void knapsack()
{
//初始化动态规划表
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < m + 1; j++)
{
p[i][0] = 0;
p[0][j] = 0;
}
}
for (int i = 1; i < n + 1; i++) //物品种类1-n
{
for (int j = 1; j < m + 1; j++) //当前预算
{
if (j < value[i - 1]) //预算<当前物品价值
p[i][j] = p[i - 1][j];
else
{
p[i][j] = max(p[i-1][j], p[i][j - value[i - 1]] + grade[i - 1]);
}
}
}
}
void apply()
{
printf("请输入种类:\n");
scanf_s("%d", &n);
printf("请输入总预算:\n");
scanf_s("%d", &m);
printf("物品价值及等级:\n");
//定义动态价值、等级表
value = (int*)malloc((sizeof(int) * n)); //定义n个物品的价值数组
grade = (int*)malloc(sizeof(int) * n); //定义n个物品的等级数组
flag = (int*)malloc(sizeof(int) * n);
int v;
int g;
for (int i = 0; i < n; i++)
{
scanf_s("%d", &v);
value[i] = v;
scanf_s("%d", &g);
grade[i] = g;
}
p = (int**)malloc(sizeof(int*) * (n + 1));
for (int i = 0; i < n + 1; i++)
p[i] = (int*)malloc(sizeof(int) * (m + 1));
}
int max(int a, int b)
{
return a > b ? a : b;
}