背包问题（记忆化搜索法、动态规划、一维数组）

阅读量：

题目描述

现有N个物品，其中第i个物品的重量为W[i]，对应的价值为V[i]，每个物品仅有一件。现提供一个最大承重为C的背包，如何选择装入的物品组合，使得背包内所装物品的总价值达到最大？

1. 暴力递归

在面对动态规划类问题时，若无法写出正确解法，可先尝试编写暴力递归方式的实现方案。

复制代码

    int maxPrix(vector<int>& W, vector<int>& V, int C, int i)
    {
    	if (i == W.size()) return 0;
    	int rs = 0;
    	if (C >= W[i])
    		rs += max(maxPrix(W, V, C, i + 1), maxPrix(W, V, C - W[i], i + 1) + V[i]);
    	else
    		rs += maxPrix(W, V, C, i + 1);
    	return rs;
    }

这段代码逻辑较为基础，因此无需进行额外的注释说明。

2. 记忆化搜索

在搜索过程中存在大量重复计算的问题

全部评论 (0)

还没有任何评论哟~