动态规划习题解题报告1

1、本页题目全部来自两天多断续弄的成果，纯刷题，不做一点延伸，不去深度研究，连程序段都基本没写，生疏了，荒废了。失眠三天了，千金难买好睡眠，况且我没有千金，这叫我如何是好。题6挤牛奶小卡卡终于帮农夫John找到了走丢的那一头奶牛，John为了感谢小卡卡，不仅告诉了他在 Pascal山脉上可能存在Pascal圣地最大的宝藏，还说要请小卡卡喝牛奶。可是农夫John发现他家里所储藏的牛奶已经喝光了,所以要临时给奶牛挤奶。小卡卡实在是太好心了,说要帮农夫John一起挤牛奶。John答应了，他把他的n头奶牛中的n/2头（n是个偶数）分给小卡卡挤，他自己挤剩下的n/2头奶牛。但是每一头奶牛都有不同的产奶量,农

2、夫John为了让小卡卡减轻负担,他希望他们两个所挤的牛奶的总量之差最小。小卡卡得知了每头奶牛的产奶情况之后很快就解决了这个问题。Input 测试数据第一行一个整数n，n为偶数且小于100。表示有n头奶牛。 第二行n个整数分别给出每头奶牛的产奶量（产奶量的总和不超过2000）。 Output 输出小卡卡和农夫所挤的牛奶量的最小差值。Sample Input 67 9 2 6 4 2Sample Output 0【代码】别人的算法，自己做不出来，觉得写得很漂亮。#include<iostream>#include<cstring>using namespace std;bo

3、ol bag511001;int m101,a101;int n;int main() while (scanf("%d",&n)!=EOF) int sum=0; for (int i=1;i<=n;i+) scanf("%d",&ai); sum+=ai; memset(bag,false,sizeof(bag); bag00=true; memset(m,0,sizeof(m); for (int i=1;i<=n;i+) for (int j=min(i,n>>1);j>=1;j-) for (int

4、 k=min(mj-1+ai,sum>>1);k>=ai;k-) bagjk|=bagj-1k-ai; if (bagjk && mj<k) mj=k; for (int i=sum>>1;i>=0;i-) if (bagn>>1i) printf("%dn",sum-(2*i); break; return 0;题8一般性的最少硬币组成问题【分析】这些硬币若能组成价值V，必然能组成价值V-coini中的一项。【程序核心】Memset(volue,false,sizeof(volue);Volue0=tu

5、re;for(i=1V)for(j=0n-1)if(i-coinj>0)valuei|=valuei-coinj;if(valuei)break;题9多个公司间的机器分配问题【分析】状态转移方程：f(m,n)=max(f(m-0,n-1)+a0,n，f(m-m,n-1)+am,n)题102010浙江省队选拔积木城堡【算法】计算每一个城堡的高度，找到最小高度G。对每一个城堡f(i,g)，（i为城堡编号）做等同于容量为G的背包问题求解，所有背包均能装满则G为最大高度。G-对每一个城堡，由于f(i,g)已经知道，现在只需判断f(i,G)是否等于G（装满），全部是，得出结果，否则重复。题11生物基元问题【算法核心】f(0)=ture;for(i=1s)for(j=min(20,i)1)if(f(i)=(f(i-j)&&stri-j+1i) /stri-j+1i属于基元时值为真。break;/s值过大，可进行优化减少循环次数。题12双塔【分析】一时找不对路。烦了。搁着。题41过河【分析】状态转移