完全背包问题

完全背包问题之二——完全背包问题（knapsack.pas）描述：设有n种物品，每种物品有一个重量及一个价值，且每种物品的数量是无限的。同时有一个背包，，背包的最大载重量为m。请你从这n种物品中选取若干件（同一种物品可以多次选取）装入背包中，使其总重量不超过m，而价值总和最大。输入格式：knapsack.in第一行：两个整数m（背包容量）和n（物品数量）。（m≤200，n≤30）接下来的n行：每行两个整数wi（第i个物品的重量）和ui（第i个物品的价值）。wi≤200，ui≤500输出格式：knapsack.out一个整数，表示最大总价值。输入数据保证结果小于10000。输入样例：10421334579输出样例：12基本思路：完全背包问题与01背包问题非常相似，唯一不同的是每种物品可选无限件。也就是说，每种物品的策略不再是取或不取两种，而是取0件，1件，2件等很多种。与01背包问题类似，如果用f[i,v]表示前i件物品恰放入容量为v的背包，用k表示第i种物品的数量，则可写出状态转移方程：f[i,v]=max{f[i-1,v-k*w[i]]+k*u[i]|0≤k*w[i]≤v}。有了这个状态转移方程，我们的思路就比较清晰了：可以用一个三重循环，第一层枚举i，第二层枚举v，第三层枚举k。下面给出伪代码：fori:=1tondoforv:=1tomdobeginmax:=0;fork:=0tovdivw[i]doifmaxf[i-1,v-k*w[i]]+k*u[i]thenmax:=f[i-1,v-k*w[i]]+k*u[i];f[i,v]:=max;end;end;那么，是不是这样就好了呢？不幸的是，作为最容易想到的方法，它也理所当然地成为了复杂度最高的。让我们来看看它的时间复杂度：在最坏的情况下，k可能从0循环到m，所以这个算法的复杂度为O(nm2)。也就是说，需要再改进这个算法。让我们再来看看这个状态转移方程：f[i,v]=max{f[i-1,v-k*w[i]]+k*u[i]|0≤k*w[i]≤v}在f[i,v]的计算中选择k(k≥1)个的情况为f[i-1,v-k*w[i]]+k*u[i],在f[i,v-w[i]]的计算中选择k-1个的情况为f[i-1,v-w[i]-(k-1)*w[i]]+(k-1)*u[i]=f[i-1,v-k*w[i]]+(k-1)*u[i]于是我们可以进行如下变形：f[i,v]=max{f[i-1,v-k*w[i]]+k*u[i]|k≥0}=max(f[i-1,v],max{f[i-1,v-k*w[i]]+k*u[i]|k≥1)=max(f[i-1,v],max{f[i-1,(v-w[i])-k*w[i]+k*u[i]|k≥0}+u[i])=max(f[i-1,v],f[i,v-w[i]]+u[i])也就是说，我们并不需要关于k的循环。于是我们得到了新的状态转移方程：f[i,v]=max(f[i-1,v],f[i,v-w[i]]+u[i]);对比一下01背包问题的状态转移方程：f[i,v]=max(f[i-1,v],f[i-1,v-w[i]]+u[i])是不是只有细微的一点差别？所以说，01背包问题是最基本的背包问题。让我们来回顾一下之前的01背包问题：0/1背包问题是可以用一维数组来完成的。我们用w[i]表示重量，用c[i]表示价值，则用a[j]表示当包中装有j公斤质量的物品时的最大价值。Fori:=1tondo用递推求出j:=mdowntow[i]时最大的a[j]。a[j]:=a[j-w[i]]+c[i];最后求出的a[m]即最大总价值。那么我们所需要的状态转移方程是a[j]:=max{a[j-w[i]]+c[i]，w[i]=j=m,i=n};类似地，我们也可以运用一维数组来做完全背包问题。理解一下下面的伪代码：fori:=1tondoforv:=w[i]tomdoiff[v-w[i]]+u[i]f[v]thenf[v]:=f[v-w[i]]+u[i];比较一下01背包问题的伪代码：fori:=1tondoforv:=mdowntow[i]doiff[v-w[i]]+u[i]f[v]thenf[v]:=f[v-w[i]]+u[i];可以看到它们只是循环的方向不同。如果理解了01背包问题和完全背包问题，这点差别应该很容易理解。回想一下，01背包问题为什么要逆序循环？这是因为每样物品只能选一次。对于每一个i，f[v]:=max(f[v],f[v-w[i]]+u[i])v由大到小循环，而v-w[i]始终小于v，这就保证了推每一个f[v]时，所用的f[v-w[i]]都是上一个i的，也就避免了重复选择物品。而完全背包问题有无限件物品可选，正好需要v正序循环。完全背包问题还有其他多种优化方法，如把问题转化为01背包问题求解、拆分物品等，大家可以自己看书，加深理解。最小乘车费用busses.pas问题描述：某条街上每一公里就有一汽车站，乘车费用如下表：公里数12345678910费用122131404958697990101而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比一公里小的情况是允许的）。输入文件：busses.in输入文件共两行，第一行为10个不超过200的整数，依次表示行驶1~10公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公里数。输出文件：busses.out输出文件仅一行包含一个整数，表示该测试点的最小费用。输入数据保证最小费用小于10000。输入样例：12213140495869799010115输出样例：147货币系统money.pas问题描述母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统，它们对货币的数值感到好奇。母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。给出n种面值的货币系统，请你帮母牛们求出组成面值为m的货币有多少种方案。输入文件：money.in第一行为两个整数n和m，分别表示货币面值种类和要求组成的货币总面值；接下来n行表示货币的每种面值ai。n≤20，m≤4000，ai≤3000输出文件：money.out一个整数，表示方案数。（可能需使用qword）输入样例：310125输出样例：10