当时考试的时候没有弄明白,费了一天的功夫,终于解理了动态归划,过程及我的理解写下来。
一道关于动态归划的算法题:
试题四(共15分)
阅读下列说明,回答问题
1至问题3
【说某明餐】厅供应各种标准的营养套餐。假,设将菜解单答上填共入有答题纸的对应栏内。
n项食物m1,m2,…,mn食物,每项mi的营养价值为vi,价格为pi,其中i=1,2,…,n人常需要一个算法来求解总不超过,套餐中每项食物至多出现一次。客人常需要一个算法来求解总低格不超过M的营养最大的套餐。
伪代码中的主要变量说明如下:
n: 总的食物项数;
v: 营养价值数组,下标从1到n,对应第1到第n项食物的营养价值;
p: 价格数组,下标从1到n,对应第1到第n项食物的价格;
M:总价格标准,即套餐的价格不超过M;
x: 解向量(数组),下标从1到n,其元素值为0或1,其中元素值为0表示对应的食物不出现在套餐中,元素值为1表示对应的食物出现在套餐中;
nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv[i][j]表示由前i项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下:
MaxNutrientValue(n, v, p, M, x)
1 for i = 0 to n
2 nv[i][0] = 0
3 for j = 1 to M
4 nv[0][j] = 0
5 for i = 1 to n
6 for j = 1 to M
7 if j < p[i] //若食物mi不能加入到套餐中8 nv[i][j] = nv[i - 1][j]
9 else if(1)
10 nv[i][j] = nv[i - 1][j]
11 else
12 nv[i][j] = nv[i - 1][j – p[i]] + v[i]
13 j = M
14 for i = n downto 1
15 if(2)
16 x[i] = 0
17 else
18 x[i] = 1
19 (3)
20 return x and nv[n][M]
完整java代码如下:
class Max{
int max (int n, int v[], int p[], int M, int x[])
{
int i, j;
int nv[][] = new int[n+1][M+1];
for (i = 0; i <= n; i++)
nv[i][0] = 0;
for (j = 0; j <= M; j++)
nv[0][j] = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= M; j++)
{
if (j < p[i]) //(1)
nv[i][j] = nv[i-1][j];
else if (nv[i-1][j] >= (nv[i-1][j-p[i]] + v[i])) //(2)
nv[i][j] = nv[i-1][j];
else
nv[i][j] = nv[i-1][j-p[i]] + v[i];
}
j = M;
for (i = n; i >=1; i--)
{
//if ( (nv[i-1][j-p[i]] + v[i]) < nv[i][j] || j<=0)
if(nv[i][j] == nv[i-1][j])
x[i] = 0;
else
{
x[i] = 1;
j = j - p[i];
}
}
return nv[n][M];
}
}
public class MaxValue {
public static void main(String[] args) {
int n = 5, M = 100;
//int nv[][] = new int[n+1][M+1];
int x[] = {0, 0, 0, 0, 0, 0};
int p[] = {0, 50, 30, 45, 25, 5};
int v[] = {0, 200, 180, 225, 200, 50};
Max m = new Max();
m.max(n, v, p, M, x);
System.out.println("应选取的食物为:");
for (int i = 1; i < 6; i++)
{
if (x[i] == 1)
System.out.println(i);
}
System.out.println("产生的最大营养价值为:" + m.max(n, v, p, M, x));
}
}
(1) 此处比较是为了确定位置的价格是否可以购买当前行标准的食物,如果钱不够买,那么就使用前一行数组对应当前列的值(花的钱一样多)作为最大的营养标准(你都买不起,还用考虑这类标准的食物吗?)。如果钱够了,可以买得起了,那么就得考虑是否要购买这类食物,买了会不会有利于组合出最大的营养价值出来,也就进入了下面的一组判断。
(2) 重要是这个判断,首先要理解的是以下几个式子的意思:
j-p[i]表示在当前的价格标准下,把当前食物加入套餐后还剩余的钱( j为当前价格标准,p[i]当前食物的价格)
nv[i - 1, j - p[i]] + v[i]是把当前价格标准的食物买入的情况下产生的营养价值,如果买入了当前价格标准的食物,那么会多产生v[i]的营养价值,剩余的钱为j - p[i],那点剩余的钱对应的最大营养价值为不包含当前价格标准的食物下价格为j - p[i]的最大营养价值,也就是前一行数组中第j - p[i]的值,比较这两个位置的值后,就可以确定是否需要包含当前价格标准的食物了。如果nv[i - 1, j]的值大,就不包含当前价格标准的食物,反之则包含当前价格标准的食物,最大营养价值为nv[i - 1, j - p[i]] + v[i]。
因为nv[i-1,j-p[i]]+v[i]很可能小于不加入食物i时的营养值,即nv[i-1,j]
这里如果没仔细想可能还不明白,为什么加了当前食物的营养值还会小于不加入的呢?因为要受到一个价格因素的影响,如果当前食物的价格很高,而营养值却不太高,而如果不加入这个食物,省下的钱可以买几个食物,这几个食物的营养值之和可能更大。nv[x,y]代表在x项食物中选择的价格小于y的营养值最高的套餐的营养值 .所以nv[i,j]的值就要从nv[i - 1, j-p[i]] + v[i] 和nv[i-1][j]里面选一个较大值.任何一个套餐的最高营养值都是这两个值中的最大值。
分享到:
相关推荐
上午题目和答案完全,可信! 下午题有一道完整的算法题和参考答案
高精度动态称重算法与实现 高精度动态称重算法与实现 高精度动态称重算法与实现
首先,"JAVA经典算法40题.doc"可能包含了一些基础的算法题目,如排序(冒泡排序、选择排序、插入排序、快速排序、归并排序)、搜索(线性搜索、二分搜索)、图论(最短路径问题、拓扑排序)以及动态规划等。...
本书覆盖了从排序和搜索到图算法,再到动态规划和贪心算法等一系列广泛的主题,旨在帮助学生和从业者提升算法思维能力,解决实际问题。 本书的习题解答部分是学习过程中不可或缺的辅助资料。每一道习题都是对理论...
这本书涵盖了各种基础和高级算法,包括排序、搜索、图算法、动态规划等,是许多大学计算机科学课程的参考教材。提供的压缩包文件“习题答案”很可能包含了该书各章节习题的解答,对于学习者来说,是一份非常有价值的...
计算机算法设计与分析是计算机科学领域的一门核心课程,它主要关注如何有效地设计、分析以及实现算法。这门课程的目的是培养学生的逻辑思维能力、问题解决能力和编程技能,以应对复杂计算问题。在这个压缩包中,包含...
在这个主题中,我们涵盖了数组、链表、栈、队列、树、图、哈希表等基本数据结构,以及排序、查找、递归、贪心、动态规划和分治等经典算法。以下是对每章练习答案的详细讨论: 1. **数组**:数组是最基础的数据结构...
在某些情况下,完全确定性的算法可能难以实现或效率低下,这时可以采用概率算法或随机化算法。本章会探讨这类算法的基本思想,如蒙特卡洛方法和拉斯维加斯方法。 每章的课后习题设计得既具有挑战性,又能够帮助...
java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题
《算法设计与分析》是计算机科学领域的一本经典教材,由吕国英教授编写,它深入浅出地讲解了如何设计高效且实用的算法,并对这些算法进行了严谨的分析。书中的第三章、第四章和第五章分别涵盖了不同的算法主题,而...
C++算法大全及面试题详解资料包包含两个word文档,一个C++算法大全,一个C++面试经典题及答案详解(包含大量代码)。这两份资料整理了C++的常见算法、常见考点和重要知识技巧,内容齐全,涵盖各类应试考点,满满干货...
该试题旨在考察学生对动态规划算法的理解和应用能力,要求学生能正确地使用动态规划算法实现0-1闭包问题。 …(其他试题) 本资源旨在帮助学生更好地理解和掌握算法设计与分析的知识,为期末考试总复习提供了多个...
本资源“用C/C++实现的各种经典算法以及常见面试题”正是针对这两方面的学习和提升。 首先,经典算法是计算机科学的基础,包括排序、查找、图论、动态规划等。例如: 1. **排序算法**:快速排序、归并排序、堆排序...
2. **链表**:每个元素(节点)包含数据和指向下一个节点的引用,适合动态存储。 3. **栈**:后进先出(LIFO)的数据结构,常用于函数调用和表达式求值。 4. **队列**:先进先出(FIFO)的数据结构,适用于任务调度...
设计和实现关于内存管理的内存布局初始化及内存申请分配、内存回收等基本功能操作函数,尝试对用256MB的内存空间进行动态分区方式模拟管理。内存分配的基本单位为1KB,同时要求支持至少两种分配策略,并进行测试和对...
《算法分析与设计》是由屈婉玲等作者编写的教材,该书深入浅出地讲解了算法设计的基本原理和分析方法。课下习题是学习过程中不可或缺的一部分,它们旨在帮助学生巩固理论知识,提高实际问题解决能力。这些习题答案...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
《计算机算法设计与分析导论》(Sara Baase,第三版)课后习题答案涵盖了算法设计与分析的基本概念和方法,我们讨论了 Maxsort 算法和冒泡排序算法这两种排序算法,并介绍了算法设计与分析的方法。通过学习这些内容...
python算法趣味题目.doc
这份资源包含的"JAVA基础编程练习题50题及经典算法90题"是学习和提升Java技能的理想材料。以下将分别介绍这些题目可能涵盖的知识点。 一、Java基础编程练习题50题: 这50题主要针对Java语法、数据类型、控制结构、...