AcWing 3. 完全背包问题-(C语言实现)
原题链接
简单
作者:
CoderXx
,
2024-01-19 20:44:00
,
所有人可见
,
阅读 41
C 代码
#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b)) ? (a) : (b)
int main()
{
int n, v;
int *dp = NULL; /* dp[j]:容量为j的物品,可以放置物品最大价值为dp[j] */
int **goods = NULL;
scanf("%d %d", &n, &v);
/* 输入物品:体积 价值 */
goods = (int **)malloc(sizeof(int *) * (n + 1));
for(int i = 0; i <= n; i++)
{
goods[i] = (int *)calloc(2, sizeof(int));
if(i > 0)
scanf("%d %d", &goods[i][0], &goods[i][1]);
}
/* 初始化dp数组 */
dp = (int *)calloc(v + 1, sizeof(int));
for(int i = 1; i <= n; i++) /* 遍历物品 */
{
for(int j = 1; j <= v; j++) /* 遍历容量 */
{
if(j >= goods[i][0])
dp[j] = MAX(dp[j], dp[j - goods[i][0]] + goods[i][1]);
}
}
printf("%d\n", dp[v]);
free(dp);
return 0;
}