高级中学信息技术算法与程序设计问答题每日一练(2019.12.16)

问答题
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
答案：举例如：
p{7，4，4}，w={3，2，2}，c=4时，
由于7/3最大，
若按题目要求...
问答题
输入某年，某月，某日，判断这一天是这一年的第几天。
答案：#include
void main()
{
int y,m,d;
问答题
已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）的非递归表达式为：现有Hanoi塔问题的递归方程为：，求h（n）的非递归表达式。
答案：
利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：
问答题
通过键盘输入一个高精度的正整数n（n的有效位数≤240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】 178543 S=4 【样例输出】 13
答案：为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位...
问答题
描述0-1背包问题。
答案：已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总...