利用动态规划算法解01背包问题->二维数组传参->cpp内存管理->堆和栈的区别->常见的内存错误及其对策->指针和数组的区别->32位系统是4G

2018-10-31 1160

简介： 1、利用动态规划算法解01背包问题 https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html 两层for循环，依次考察当前石块是否能放入背包。

+关注继续查看

1、利用动态规划算法解01背包问题

https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

两层for循环，依次考察当前石块是否能放入背包。如果能，则考察放入该石块是否会得到当前背包尺寸的最优解。

// 01 knapsack problem dynamic programming algorithm

#include "pch.h"
#include <iostream>

void dynamic_program( int stone_num, int knapsack_capacity, int stone_weight[],  
	int stone_value [], int stone_in_or_not [], int (*V)[8]) {

	//栈内存需要初始化
	memset(V, 0, sizeof(V));

	for (int i = 0; i < stone_num; i++) {
		for (int j = 1; j <= knapsack_capacity; j++) {
			//此时背包无法装入当前石块
			if (j < stone_weight[i]) {
				V[i][j] = V[i - 1][j];
			}
			else {
				//不装入价值更大
				if (V[i - 1][j] > (V[i - 1][j - stone_weight[i]] + stone_value[i])) {
					V[i][j] = V[i - 1][j];
				}
				else {
					//前i-1个物品的最优解与第i个物品的价值之和最大
					V[i ][j] = (V[i - 1][j - stone_weight[i]] + stone_value[i]);
					stone_in_or_not[i] = 1;
				}
			}
		}
	}
	int a = 0;
}
void init() {
	int stone_num = 4, knapsack_capacity = 8;
	int stone_weight[] = { 2, 3, 4, 5 };
	int stone_value[] = { 3, 4, 5, 6 };
	int stone_in_or_not[] = { 0,0,0,0,0,0,0,0 };
	int V[4][8];
	dynamic_program(stone_num, knapsack_capacity, stone_weight, stone_value, stone_in_or_not, V);

}
int main()
{
    init();
	return 0;
}

2、二维数组传参

https://blog.csdn.net/yunyun1886358/article/details/5659851

int main()
{
    int m = 10;
    int n = 10;
    int** p = new int[m][n];
}

会发现编译不通过，第二个维度长度必须为常量。那么怎么声明一个两个维度都能动态指定的二维数组呢？看下面：

void func5(int** pArray, int m, int n)
{

}

#include <ctime>
int main()
{
    int m = 10;
    int n = 10;

    int** pArray = new int* [m];
    pArray[0] = new int[m * n]; // 分配连续内存

    // 用pArray[1][0]无法寻址，还需指定下标寻址方式
    for(int i = 1; i < m; i++)
    {
        pArray[i] = pArray[i-1] + n;
    }

    func5(pArray, m, n);
}

这里为二维数组申请了一段连续的内存，然后给每一个元素指定寻址方式（也可以为每一个元素分别申请内存，就不必指定寻址方式了），最后将双重指针作为实参传递给func5。这里func5多了两个形参，是二维数组的维度

3、堆和栈的区别

主要区别有以下几点

（1）管理方式不同（2）空间大小不同（3）能否产生碎片不同（4）生长方式不同

（5）分配方式不同（6）分配效率不同

4、常见的内存错误及其对策

（1）内存分配未成功，却使用了它。因为内存分配会不成功。

常用解决办法是，在使用内存之前检查指针是否为NULL。

如果指针p是函数的参数，那么在函数的入口处用assert(p!=NULL)进行检查。

如果是用malloc或new来申请内存，应该用if(p==NULL) 或if(p!=NULL)进行防错处理。

（2）内存分配虽然成功，但是尚未初始化就引用它。

内存的缺省初值究竟是什么并没有统一的标准，尽管有些时候为零值，我们宁可信其无不可信其有。所以无论用何种方式创建数组，都别忘了赋初值，即便是赋零值也不可省略，不要嫌麻烦。

（3）内存分配成功并且已经初始化，但操作越过了内存的边界。

例如在使用数组时经常发生下标“多1”或者“少1”的操作。特别是在for循环语句中，循环次数很容易搞错，导致数组操作越界。

（4）忘记了释放内存，造成内存泄露。

含有这种错误的函数每被调用一次就丢失一块内存。刚开始时系统的内存充足，你看不到错误。终有一次程序突然死掉，系统出现提示：内存耗尽。动态内存的申请与释放必须配对，程序中malloc与free的使用次数一定要相同，否则肯定有错误（new/delete同理）。

（5）释放了内存却继续使用它。发生该情况有三种可能：

1). 程序中的对象调用关系过于复杂，实在难以搞清楚某个对象究竟是否已经释放了内存，此时应该重新设计数据结构，从根本上解决对象管理的混乱局面。

2). 函数的return语句写错了，注意不要返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。

3). 使用free或delete释放了内存后，没有将指针设置为NULL。导致产生“野指针”。

那么如何避免产生野指针呢？这里列出了5条规则，平常写程序时多注意一下，养成良好的习惯。

规则1：用malloc或new申请内存之后，应该立即检查指针值是否为NULL。防止使用指针值为NULL的内存。

规则2：不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右值使用。

规则3：避免数组或指针的下标越界，特别要当心发生“多1”或者“少1”操作。

规则4：动态内存的申请与释放必须配对，防止内存泄漏。

规则5：用free或delete释放了内存之后，立即将指针设置为NULL，防止产生“野指针”。

5、指针和数组的区别

下面示例中，字符数组a的容量是6个字符，其内容为 hello。a的内容可以改变，如a[0]= ‘X’。指针p指向常量字符串“world”（位于静态存储区，内容为world），常量字符串的内容是不可以被修改的。从语法上看，编译器并不觉得语句p[0]= ‘X’有什么不妥，但是该语句企图修改常量字符串的内容而导致运行错误。