动归DP算法学习笔记 01背包 C++代码注解

本文主要是介绍动归DP算法学习笔记 01背包 C++代码注解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包问题是动态规划的经典问题, 也是基础问题。

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <stdarg.h>
#include <stddef.h>
#include "inputf.h"
int knapsack_2d(int v, int n, const int *c, const int *p)
{int *s = (int *)malloc(n * v * sizeof(int));#define f(a,b) (*(s + (a) * v + (b)))//int(*d)[8][100] = (int(*)[8][100])s;int nn = n, vv = v;while (--nn >= 0){vv = v;while (--vv >= 0){if (nn + 1 < n) {f(nn, vv) = f(nn + 1, vv);if (vv + 1 >= c[nn]) {int l = (vv + 1 > c[nn] ? f(nn + 1, (vv - c[nn])) : 0) + p[nn];if (l > f(nn, vv)) f(nn, vv) = l;}} else {f(nn, vv) = vv + 1 >= c[nn] ? p[nn] : 0;}}}v = f(0, v - 1); // 此处仅仅为了保存 v = f(0, v - 1) 的值free(s);return v;
}
/** 01背包问题 总价值最大 一维解法* 返回 h = max{ f[1...n] }*/

这篇关于动归DP算法学习笔记 01背包 C++代码注解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---