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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

王小闹儿 2018-10-31 23:26:46 浏览367
展开阅读全文

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’有什么不妥,但是该语句企图修改常量字符串的内容而导致运行错误。

 

6、32位系统是4G

https://blog.csdn.net/nvd11/article/details/8749375

 

7、各种getmemory

https://blog.csdn.net/u010027547/article/details/52292889

 

参考文献:

assert()函数 :  https://www.cnblogs.com/lvchaoshun/p/7816288.html

cpp内存管理:  https://chenqx.github.io/2014/09/25/Cpp-Memory-Management/

二维数组传参:  https://blog.csdn.net/yunyun1886358/article/details/5659851

动态规划算法解决01背包问题: https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

网友评论

登录后评论
0/500
评论
王小闹儿
+ 关注