完全背包专题训练(Pascal)
第6课竞赛总分(inflate)
【问题描述】
学生在USACO竞赛中得分越多我们越高兴。我们试着设计竞赛以便学生尽可能多得分。现在要进行一次竞赛，总时间T固定，有若干类型可选的题目，每种类型题目可选入的数量不限，每种类型题目有一个S1（解答此题所得的分数）和ti（解答此题所需的时间），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大。
【输入格式】
第1行：两个整数，竞赛的时间t(1≤t≤10000)和题目类型数n(1≤n≤10000)；
第2～n+1行：两个整数，每种类型题目的分数和耗时。第一个整数说明解决这种题目能得的分数(1≤S1≤10000)，第二个整数说明解决这种题目所需的时间(1≤ti≤10000)。
【输出格式】
单独的一行，在给定时间里得到的最大总分。
【输入样例】
3004
10060
250120
120100
3520
【输出样例】
605
样例说明：从第2种类型中选两题和第4种类型中选三题。
分析问题
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i，j]表示前i种物品放入容量为j的背包的最大值，可得状态转移方程如下：
f[i,j]=max{f[i-l,j-k×t[i]]+k×s[i]10≤k×t[i]≤T}
这跟01背包问题一样有O(n×T)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i，j]的时间是O(T/t[i])，总的复杂度约为O(T×n×ave(T/t[i]))，ave(T/t [i])表示T/t[i]的平均值。
解决问题
我们将01背包问题一维的实现方法的基本思路加以改进。首先想想，为什么01背包程序中要按照for j:=T downto t[i]do来循环？这是因为要保证第i次循环中第i件物品只选一次，保证在考虑“选入第i件物品”时，依据的是一个从未选过第i件物品的子结果g[j-t[i]]。
现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”时，正需要一个可能已选入第i种物品的子结果g[j-t[i]]，所以就可以采用for j:=t[i]to T do 的顺序循环。状态转移方程如下：
g j=max{g[j],g[j-t[i]])(1≤i≤n,t[i]≤j≤T)
该算法的时间复杂度为O(n×T)。
参考程序如下：
var g:array[0..10002]of longint;
n,time,i,j:integer;
s,t:array[1..10000]of integer;
begin
readln(time,n);
for i:=1to n do readln(s[i],t[i]);
for i:=1to n do
for j:=t[i]to time do
if g[j] writeln(g[time]); end. 活学活用 1．货币系统(money) 【问题描述】 母牛们不但创建了它们自己的政府，而且选择建立了自己的货币系统。它们对货币的数值感到好奇。传统地，一个货币系统是由1，5，10,20或25,50,100的单位面值组成的。母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。 举例来说，使用一个货币系统{1,2，5，10，…}产生18单位面值的一些可能的方法是：18×1,9×2,8×2+2×1,3×5+2+1等等。写一个程序，计算用给定的货币系统来构造一个确定的面值有多少种方法。 【输入格式】 第1行有两个整数n，v，其中v(1≤v≤25)表示货币系统中货币的种类，n是要构造的面值 (1≤n≤10000)； 第2～v+l行：表示可用的货币面值（每行一个）。 【输出格式】 输出方案总数。 【输入样例】 310 1 2 5 【输出样例】 10 2．金银岛(coin) 【问题描述】 在金银岛上，人们使用的货币的值都是完全平方数，例如1,4,9,…,289。支付十元钱有下列四种方法： (1)十个一元的钱； (2)一个四元的，六个一元的； (3)两个四元的，两个一元的； (4)一个九元的，一个一元的。 你的任务是对于给定的钱数（设其值少于300），求出支付方法的总数。 【输入格式】 输入共有n+l行（n未知），以数字O结束，每行为一个自然数t(1≤t≤300)。 【输出格式】 输出共有n行，每行表示对于给定的钱数t，对应的支付方案总数。 【输入样例】 2 10 30 【输出样例】 1 4 27 3．质数和分解(resolve) 【问题描述】 任何大于l的自然数n，都可以写成若干个大于等于2且小于等于n的质数之和的形式f （包括只有一个数构成的和表达式的情况），并且可能有不止一种质数和的形式。例如9的质数和表达式就有四种本质不同的形式：9=2+5+2=2+3+2+2=3+3+3=2+7。 这里所谓两个本质相同的表达式，是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。试编程求解自然数n可以写成多少种本质不同的质数和的表达式。 【输入格式】 每一行存放一个自然数n(2≤n≤200)。 【输出格式】 输出自然数n的本质不同的质数和表达式的数目。 【输入输出样例】 输入输出 样例121 样例22009845164 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据： 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。 总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗? 下面是实际程序: #include 兰州交通大学数理与软件工程学院 题目0-1背包问题算法实现 院系数理院 专业班级信计09 学生姓名雷雪艳 学号200905130 指导教师李秦 二Ｏ一二年六月五日 一、问题描述： 1、0—1背包问题：给定n 种物品和一个背包，背包最大容量为M ，物 品i 的重量是w i ,其价值是平P i ，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？ 背包问题的数学描述如下： 2、要求找到一个n 元向量(x1，x2…xn)，在满足约束条件： ????? ≤≤≤∑1 0i i i x M w x 情况下，使得目标函数 p x i i ∑max ，其中，1≤i ≤n ；M>0； wi>0；pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数 达到最大的那个可行解则为最优解[1]。 给定n 种物品和1个背包。物品i 的重量是wi ，其价值为pi ，背包的容量为M 。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i 只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i 。该问题称为0-1背包问题。 0-1背包问题的符号化表示是，给定M>0， w i >0， pi >0，1≤i ≤n ，要求找到一个n 元0-1向量向量(x1，x2…xn)， X i =0 或1 , 1≤i ≤n, 使得 M w x i i ≤∑ ，而且 p x i i ∑达到最大[2]。 二、解决方案： 方案一：贪心算法 1、贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。 贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 2、0-1背包问题的实现 对于0-1背包问题，设A 是能装入容量为c 的背包的具有最大价值的物品集合，则Aj=A-{j}是n-1个物品1,2,...,j-1,j+1,...,n 可装入容量为c-wj 的背包的具有最大价值的物品集合。 用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi ；然后，将物品进行排序，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c ，则选择单位重量价值次高的物品并尽可能多地装入背包。 P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 优化空间复杂度 以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么 Pascal语言编程基础程序 （常州市） 十进制转二进制 var i,n,j:longint; a:array[1..100] of longint; begin readln(n); i:=1; while n<>0 do begin a[i]:=n mod 2; i:=i+1; n:=n div 2; end; write('Bin:'); for j:= i-1 downto 1 do write(a[j]) end. 数组元素删除 var a:array[1..10]of longint; i,t,x:longint; begin read(x); for i:=1 to 10 do a[i]:=2*i-1; t:=a[x]; for i:=x+1 to 10 do a[i-1]:=a[i]; for i:=1 to 9 do write(a[i]:4); end. 数组元素删除2 var a:array[1..11]of longint; i:longint; begin for i:=1 to 10 do a[i]:=i; a[11]:=a[1]; for i:= 1 to 10 do a[i]:=a[i+1]; for i:= 1 to 10 do write(a[i]:4); end. 数组元素的移动 var a:array[1..10] of longint; s,n,i,x,t:longint; begin readln(n); for i:=1 to n do read(a[i]); readln(x); s:=a[x]; for i:=x+1 to n do a[i-1]:=a[i]; for i:=1 to n-1 do write(a[i],' '); write(s); end. 排除所有异形基因 var a:array[1..100] of longint; n,g,j,i,wz:longint; begin readln(n); for i:=1 to n do read(a[i]); g:=0; for i:=1 to n do if sqr(a[i]) mod 7=1 then begin wz:=i; for j:=wz+1 to n do a[j-1]:=a[j]; g:=g+1 end; write(a[1]); for i:=2 to n-g do write(' ',a[i]); writeln; end. 排除第一个异形基因 var a:array[1..100] of longint; n,i,wz:longint; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do if sqr(a[i]) mod 7=1 背包 它是在1978年由Merkel和He llman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。 DD牛的背包九讲 P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}。 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f [v-c]再加上通过放入第i件物品获得的价值w。 注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢？f[v]是由f[v]和f [v-c]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c]+w}; 其中的f[v]=max{f[v],f[v-c]}一句恰就相当于我们的转移方程f[v]=max{f[v],f[v-c]}，因为现在的f[v-c]就相当于原来的f[v-c]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[v]由f[v-c]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 总结 01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想， f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]} 第一讲 01背包问题 题目 有N 件物品和一个容量为V 的背包。第i 件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价 值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i 件物品恰放入一个容量为v 的背包可以获得的最大价值。则其状态转移方程便是： 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i 件物品放入容量为v 的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i 件物品，那么问题就转化为“前i-1件物品放入容量为v 的背包中”，价值为f[i-1][v]；如果放第i 件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i 件物品获得的价值 w[i]。 优化空间复杂度 以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以 优化到O 。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N ，每次算出来二维数组f[i][0..V]的所有 值。那么，如果只用一个数组f[0..V]，能不能保证第i 次循环结束后f[v]中表示的就是我们定义的状态f[i][v] 呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i 次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推 f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v 的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 目录 第一部分 PASCAL语言程序设计 (1) 第一章 PASCAL语言基础 (1) 第一节程序的组成与上机调试运行 (2) 第二节常量、变量与数据类型 (3) 第三节表达式与标准函数 (6) 第四节赋值语句、输入与输出语句 (9) 习题 (12) 第二章程序的三种基本结构 (15) 第一节顺序结构 (15) 第二节选择结构 (15) 第三节循环结构 (17) 习题 (20) 第三章数组 (22) 第一节一维数组 (22) 第二节二维数组及应用 (25) 习题 (26) 第四章字符与字符串操作 (29) 第一节字符和字符数组 (29) 第二节字符串变量 (29) 第三节字符串应用举例 (31) 习题 (33) 第五章函数与过程 (35) 第一节自定义函数 (35) 第二节自定义过程 (38) 第四节递归 (42) 第五节递归与回溯 (45) 习题 (50) 第一部分 PASCAL语言程序设计 第一章 PASCAL语言基础 Pascal语言是瑞士苏黎士工科大学的Niklans Wirth（沃思）1971年发表的，是为了纪念17世纪法国著名哲学和数学研究者Blaisc Pascal而将它命名为Pascal程序设计语言。Pascal语言是信息学奥赛中普遍使用的程序设计语言。 第一节程序的组成与上机调试运行 一、程序的组成 我们先看一道例题。 例1-1 输入两个整数a和b，计算a和b的和（a+b）。 【参考程序】 program a1(input,output); //程序首部 var a,b,c:integer; //程序说明部分，a,b,c被说明为整型变量 begin //程序执行部分，下面是程序的内容 write('a='); //在屏幕上输出一个字符串“a=”，输出完后不换行 read(a); //从键盘输入一个数值赋给变量a write('b='); //在屏幕上输出一个字符串“b=”，输出完后不换行 read(b); //从键盘输入一个数值赋给变量b c:=a+b; //计算a+b的和，并将这个和赋值给变量c writeln(a,'+',b,'=',c); //输出a+b=c的等式，输出完后换行 end. //程序结束 【样例输入】 a=10 b=30 【样例输出】 10+30=40 由上可以看出，一个Pascal程序由以下三部分组成： （1）由Program 引导的一行是Pascal程序的首部。 程序首部指出了源程序的名称，是由用户自己给出的，该例子称为a1。程序名后用括号括住的两个参数input与output，通常表示程序运行中的标准输入和输出文件，程序首部以分号结束。 （2）Pascal程序的第二部分是说明部分。 说明部分要求列出程序中引用的全部常量、变量、转移标号、类型、过程和函数的有关说明。若变量c在说明部分没有说明，后边的语句c:=a+b在执行时；翻译软件便能指出其错误并提醒用户加以改正，程序中每个语句都以分号表示结束。 （3）程序的第三个部分是用BEGIN和END括住的一串语句，称为程序的执行部分。有的书中将说明部分和执行部分合称为程序体。 二、PASCAL语言编辑软件的基本操作 下面我们以Free Pascal 1.10系统为例来学习一下Pascal语言编辑软件的使用。 1.Free Pascal的启动 在运行程序目录下(一般是c:\pp\bin\go32v2)运行启动程序fp.exe，即可启动系统。屏幕上出现如图1-1所示的集成环境。 图1-1 2.Free Pascal系统集成开发环境(IDE)简介 最顶上一行为主菜单，中间蓝色框内为编辑窗口，在编辑窗口内可以进行程序的编辑，最底下一行为提示行，显示出系统中常用命令的快捷键，如将当前编辑窗口中文件存盘的命令快捷键为F2，打开磁盘文件命令F3，等等。 背包问题九讲2.0RC1 崔添翼(Tianyi Cui)* 2011-09-28? 本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。 这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发布到网上，转载众多，有一定影响力。 2011年9月，本系列文章由原作者用L A T E X重新制作并全面修订，您现在看到的是2.0alpha版本，修订历史及最新版本请访问https://https://www.wendangku.net/doc/5013006132.html,/tianyicui/pack查阅。 本文版权归原作者所有，采用CC BY-NC-SA协议发布。 Contents 101背包问题3 1.1题目 (3) 1.2基本思路 (3) 1.3优化空间复杂度 (3) 1.4初始化的细节问题 (4) 1.5一个常数优化 (4) 1.6小结 (5) 2完全背包问题5 2.1题目 (5) 2.2基本思路 (5) 2.3一个简单有效的优化 (5) 2.4转化为01背包问题求解 (6) 2.5O(V N)的算法 (6) 2.6小结 (7) 3多重背包问题7 3.1题目 (7) 3.2基本算法 (7) 3.3转化为01背包问题 (7) 3.4可行性问题O(V N)的算法 (8) *a.k.a.dd_engi ?Build20110928183800 1 3.5小结 (9) 4混合三种背包问题9 4.1问题 (9) 4.201背包与完全背包的混合 (9) 4.3再加上多重背包 (9) 4.4小结 (10) 5二维费用的背包问题10 5.1问题 (10) 5.2算法 (10) 5.3物品总个数的限制 (10) 5.4二维整数域N2上的背包问题 (11) 5.5小结 (11) 6分组的背包问题11 6.1问题 (11) 6.2算法 (11) 6.3小结 (12) 7有依赖的背包问题12 7.1简化的问题 (12) 7.2算法 (12) 7.3较一般的问题 (12) 7.4小结 (13) 8泛化物品13 8.1定义 (13) 8.2泛化物品的和 (13) 8.3背包问题的泛化物品 (14) 8.4小结 (14) 9背包问题问法的变化14 9.1输出方案 (15) 9.2输出字典序最小的最优方案 (15) 9.3求方案总数 (15) 9.4最优方案的总数 (16) 9.5求次优解、第K优解 (16) 9.6小结 (17) 2 背包问题系列算法详解 背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。 一、0-1背包问题 有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 （1）递归求解 算法如下： #include "iostream" #define CAPACITY 10 #define GOODSNUM 6 using namespace std; int nVol[GOODSNUM]; int nValue[GOODSNUM]; int knapsack(int itemIndex,int vol); void main() { int i=0,j=0; while(i 第一章PASCAL程序设计基础 我们日常工作、学习和生活中，要做某件事，如果事先没有计划，只是想一步做一步，是达不到理想效果的。要很好地、高效率地完成某件事，必须事先有一个计划，第一步做什么，下一步做什么，最后一步做什么。即先考虑好做这件事的所有步骤，然后按部就班地完成它。在计算机系统中，能完成某项任务的一系列指令或语句就是程序。程序设计是设计、书写和调试程序的过程。 第一节程序设计语言及算法 一、程序设计语言 人们使用计算机，可以通过某种计算机语言与其交谈，用计算机语言描述所要完成的工作。为了完成某项特定任务用计算机语言编写的一组指令序列就称之为程序。编写程序和执行程序是利用计算机解决问题的主要方法和手段。程序设计语言是用来书写计算机程序的语言。程序设计语言经历了机器语言、汇编语言、高级语言到面向对象的程序设计语言等多个阶段。 1.机器语言 机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活、直接执行和速度快等特点。 用机器语言编写程序,编程人员要首先熟记所用计算机的全部指令代码和代码的涵义。手编程序时,程序员得自己处理每条指令和每一数据的存储分配和输入输出,还得记住编程过程中每步所使用的工作单元处在何种状态。这是一件十分繁琐的工作,编写程序花费的时间往往是实际运行时间的几十倍或几百倍。而且编出的程序全是些0和1的指令代码,直观性差,还容易出错。现在,除了计算机生产厂家的专业人员外,绝大多数程序员已经不再去学习机器语言了。 2.汇编语言 为了克服机器语言难读、难编、难记和易出错的缺点,人们就用与代码指令实际含义相近的英文缩写词、字母和数字等符号来取代指令代码(如用ADD表示运算符号“＋”的机器代码),于是就产生了汇编语言。汇编语言是一种用助记符表示的仍然面向机器的计算机语言。汇编语言像机器指令一样,是硬件操作的控制信息,因而仍然是面向机器的语言,使用起来还是比较繁琐费时,通用性也差。汇编语言是低级语言。 3.高级语言 20世纪50年代后期，在对低级语言的改进过程中，又研制出一种既接近于自然语言，又接近数学语言的程序设计语言。使用这种语言编写程序快捷方便，便于修改和高度，大大提高了编程的效率，同时这种语言编写的程序不依赖具体的机器，能用性好，我们称之为高级语言。用高级语言，不必考虑机器的结构和特点，可以集中精力考虑解决问题的算法，因此，高级语言也称为算法语言。 4.面向对象的程序设计语言 Turbo Pascal图形编程教程Pascal是一款有很强图形功能的开发工具，它可以编制各种图形窗口,并且听说还支持鼠标.但是时过境迁，在vb,vc一统天下的今天，关于Pascal图形操作的书已经像古董一样难于寻找了，我现在将Tp 7.0的Help文件中的一些有关图形操作的过程与函数整理了一下，并自己写了一些例子,加入了一些自己的看法,便得到了这篇教程.其中如有错误，望各位不吝赐教。阅读之前希望大家做好准备，比如：找一些食品放在跟前，因为你可能因为钻研一个函数而耗费大量的时间，还有你可能因为初始化无法完成而大动肝火。 第一章使用Pascal进行图形操作前的准备 在 Turbo Pascal 中有一个 CRT 单元及一个 GRAPH 单元，简单的说 crt 单元是为了实现字符的显示与处理，另外的那个称为 GRAPH 单元是专门用来处理图形的。我们看到的有关图形的程序往往都要用到。所以若是要在 Turbo Pascal 中实现图形操作，就必须要调用 CRT 单元及 GRAPH 单元。那么怎么样来调用 CRT 及 GRAPH 单元呢？现在线来介绍一下单元调用语句：USES USES的语法： USES 单元表识符，……，单元表识符； 说明： 扩展名为*.TPW是Windows下的单元文件，*.TPU是DOS下的单元文件。 位置：变量说明var之前。 讲到这里，我还是要顺便提一下什么是单元？是这样的：我们在编程序的时候，要用到procedure 或者function ，中文名称一个是过程另一个是函数。做不同的程序时，往往要用到一些相同的过程或者相同的函数。如果统统放到程序中，程序会硕大无比，比例与调试与编译，并且在过去“惜ｋｂ如金”的年代里，这样的程序也很浪费。于是，简单的讲，人们把它们做成“包”－－我们称之为单元。一来，免去很多重复的痛苦，大家共享代码也很简单，另外，很多不愿意让别人看到源程序的人也很乐于如此－－－－这只是我的杜撰。生产pascal 语言的公司也提供一些做好的单元，放在安装盘上方便实用。crt ，graph 即使如此，还有dos ，system 等等。 第二章 Pascal图形模式的初始化及退出 1.初始化 Pascal的图形操作在使用之前必须先进行初始化。如果说你编写图形程序中出现问题，十有八九是卡在这里了。这也是非常令我头疼的问题。用过程 initgraph(GraphDriver,GraphMode,PathToDriver) 其中GraphDriver,GraphMode为整形变量,PathToDriver为字符串变量,GraphDriver为图形驱动器,GraphMode为图形模式,PathToDriver指定的路径名中建筑图形驱动程序(以.BGI为后缀)。initgraph使 用方法见下例: program t001 (input,output); 01背包问题 一、问题描述 一个正在抢劫商店的小偷发现了n个商品，第i个商品价值Vi美元，重Wi磅，Vi和Wi都是整数；这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅的商品，W是一个整数。 我们称这个问题是01背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下；他不能只拿走一个商品的一部分，或者把一个商品拿走多次。 二、解决方案 背包问题作为NP完全问题，暂时不存在多项式时间算法 1.动态规划 2.回溯法 3.分支界限法 三、方案详解 3.1动态规划 动态规划（Dynamic programming，DP）是一种在数学、计算机科学和经济学中使 用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 概述： 动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。 特征： 1、问题存在最优子结构 2、问题的最优解需要在子问题中作出选择 3、通过查表解决重叠子问题，避免重复计算 动态规划的设计： 1.刻画一个最优解的结构特征； 2.递归地定义最优解的值； 3.计算最优解的值，通常采用自底向上的方法； 4.利用计算的信息构造一个最优解。 问题分析 最优子结构： (1)问题分析：令f(i,j)表示在前i(0≤i 算法设计与分析 ------0/1背包问题实例研究 班级：090402 学号：20091236 姓名：王龙 一、问题描述 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 二、基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1 件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 三、优化空间复杂度 我们可以很容易的得出，以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。先考虑上面说的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i 次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题(完全背包问题)最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 （0-1）背包问题的解法小结 1．动态规划法 递推关系： – 考虑一个由前i 个物品(1≤i ≤n )定义的实例，物品的重量分别为w 1,…,w i ，价值分别为v 1，…，v i ，背包的承重量为j (1≤j ≤W )。设V [I,j]为该实例的最优解的物品总价值 – 分成两类子集： ? 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V [i -1,j ] ? 在包括第i 个物品的子集中(因此，j －w ≥0)，最优子集是由该物品和前i -1个物品中能够放进承重量为i －w j 的背包的最优子集组成。这种最忧子集的总价值等于v i +V [i -1,j -w i ] . 0]0,[时，0 当0;][0,时，0初始条件：当],1[}],1[],,1[max{],[=≥=≥<≥? ??-+---=i V i j V j w j w j j i V v w j i V j i V j i V i i i i 以记忆功能为基础的算法：用自顶向下的方式对给定的问题求解，另外维护一个类似自底向上动态规划算法使用的表格。一开始的时候，用一种“null”符号创始化表中所有的单元，用来表明它们还没有被计算过。然后，一旦需要计算一个新的值，该方法先检查表中相应的单元：如果该单元不是“null ”，它就简单地从表中取值；否则，就使用递归调用进行计算，然后把返回的结果记录在表中。 算法 MFKnapsack(I,j) //对背包问题实现记忆功能方法 //输入：一个非负整数i 指出先考虑的物品数量，一个非负整数j 指出了背包的承重量 //输出：前i 个物品的最伏可行子集的价值 //注意：我们把输入数组Weights[1..n],Values[1..n]和表格V[0..n,0..W]作为全局变量，除了行0和列0用0初始化以外，V 的所有单元都用-1做初始化。 if V[I,j]<01 if j 1、扫描识别 SCAN.BAS/SCAN.PAS/SCAN.C/SCAN.CPP 【问题描述】 “扫描识别”你知道是怎么回事吧？它的意思就是：先用扫描仪把纸上的文字扫描成一个图片，再用识别软件把那个图片中的文字识别出来，最后生成一个文本文件。这对于需要把大量的纸稿录入成电子文档的人来说，当然是非常方便的。 以现有的技术，扫描效果是比较理想的，但识别效果还不十分另人满意，经常会出现错误，尤其是当两个字形状特别接近的时候，而且，这种错误是很难用眼睛看出来的。 我们的纸稿上有一个数字串，识别之后得到的字符串保存在输入文件中，这个串可能有识别错误。已知，可能出现的错误有如下几种： 1、把数字0错误地识别为大写字母O； 2、把数字1错误地识别为小写字母l； 3、把数字2错误地识别为大写字母Z； 4、把数字5错误地识别为大写字母S； 5、把数字6错误地识别为小写字母b； 6、把数字8错误地识别为大写字母B； 7、把数字9错误地识别为小写字母q。 你的改正方案是：如果字符串中出现了上述字母，请替换为原来的数字。最后把改正之后的数字串输出。 【输入文件】 文件名：SCAN.IN 文件中只有一个字符串，表示识别后得到的字符串。串的长度不超过100。 【输出文件】 文件名：SCAN.OUT 文件中只有一个数字串，表示改正后的数字串。 【样例输入】 321lO88BqS 【样例输出】 3211088895 2、寻找2的幂 CLOSE.BAS/CLOSE.PAS/CLOSE.C/CLOSE.CPP 【问题描述】 数学上把叫2的幂，如4、8、16 32等。给定一个整数，请输出距离它最近的那个2的幂是多少。如果有两个距离相同，输出那个小的。 【输入文件】 文件名：CLOSE.IN 文件中只有一个整数。 数据范围<=1000000000000000 【输出文件】 文件名：CLOSE.OUT 文件中只有一个整数，表示距离最近的那个2的幂。 【样例输入】 17 背包问题九讲2.0beta1.2 崔添翼(Tianyi Cui)* 2012-05-08? 本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。 这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发布到网上，转载众多，有一定影响力。 2011年9月，本系列文章由原作者用L A T E X重新制作并全面修订，您现在看到的是2.0beta版本，修订历史及最新版本请访问https://https://www.wendangku.net/doc/5013006132.html,/tianyicui/pack查阅。 本文版权归原作者所有，采用CC BY-NC-SA协议发布。 Contents 101背包问题3 1.1题目 (3) 1.2基本思路 (3) 1.3优化空间复杂度 (3) 1.4初始化的细节问题 (4) 1.5一个常数优化 (4) 1.6小结 (5) 2完全背包问题5 2.1题目 (5) 2.2基本思路 (5) 2.3一个简单有效的优化 (5) 2.4转化为01背包问题求解 (6) 2.5O(V N)的算法 (6) 2.6小结 (7) 3多重背包问题7 3.1题目 (7) 3.2基本算法 (7) 3.3转化为01背包问题 (7) 3.4可行性问题O(V N)的算法 (8) *a.k.a.dd_engi ?Build20120508120900 1 3.5小结 (9) 4混合三种背包问题9 4.1问题 (9) 4.201背包与完全背包的混合 (9) 4.3再加上多重背包 (9) 4.4小结 (10) 5二维费用的背包问题10 5.1问题 (10) 5.2算法 (10) 5.3物品总个数的限制 (10) 5.4复整数域上的背包问题 (11) 5.5小结 (11) 6分组的背包问题11 6.1问题 (11) 6.2算法 (11) 6.3小结 (11) 7有依赖的背包问题12 7.1简化的问题 (12) 7.2算法 (12) 7.3较一般的问题 (12) 7.4小结 (13) 8泛化物品13 8.1定义 (13) 8.2泛化物品的和 (13) 8.3背包问题的泛化物品 (14) 8.4小结 (14) 9背包问题问法的变化14 9.1输出方案 (14) 9.2输出字典序最小的最优方案 (15) 9.3求方案总数 (15) 9.4最优方案的总数 (16) 9.5求次优解、第K优解 (16) 9.6小结 (17) 201背包问题动态规划详解
0-1背包问题四种不同算法的实现要点
背包问题九讲(很详细)
Pascal语言编程基础程序
背包问题题目及含义
noip背包问题教程(背包九讲)
PASCAL语言程序设计
背包问题九讲
背包问题系列算法详解
PASCAL程序设计
Turbo Pascal图形编程教程
01背包问题
算法设计-01背包问题的分析
背包问题
pascal编程练习题
背包问题九讲2.0(13年修订版)