NOIP 2006 普及组 复赛 happy 开心的金明
1.读完题目，模拟样例，一直很纳闷3900是怎么算出的，同种物品能买多件吗？
2.同种物体只能买一件，从题目中怎么读出该题意？反复读题，题中透着此意，但不明确。
3.模拟样例：400*5+300*5+200*2=3900
4.识别出该题是01背包问题，但发现目前所掌握的动态规划，还不足以解决该问题。
5.搜索了一通，一下两篇文章值得学习：
http://blog.csdn.net/mu399/article/details/7722810
https://wenku.baidu.com/view/b7b9c83f9b89680203d825fd.html
6.弄懂了01背包。还不急着处理本题，先将http://blog.csdn.net/mu399/article/details/7722810例子编编。编着编着，突然发现，同样是处理01背包问题，程序编起来，循环的差异却非常大，看来要好好研究。
7.附上http://blog.csdn.net/mu399/article/details/7722810例子的输入输出：
输入：
10 5 4 6 5 4 6 5 2 3 2 6
输出：
15
代码：
#include <stdio.h> #include <string.h> int fun(int a,int b){//返回最大值 if(a>b) return a; else return b; } int main(){ int w[10],v[10],n,m,i,j,f[20][20]; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d",&w[i],&v[i]); for(i=0;i<=m;i++) f[i][0]=0;//空间为0 for(i=0;i<=n;i++) f[0][i]=0;//选中个数为0 for(j=0;j<=n;j++) for(i=1;i<=m;i++) if(j<w[i]) f[i][j]=f[i-1][j]; else f[i][j]=fun(f[i-1][j],f[i-1][j-w[i]]+v[i]); printf("%d\n",f[m][n]); } 8.回到本题，看了N（<30000）表示总钱数，m（<25）范围，N*m不会超时。
9.按01背包思路，进行编写，样例通过，提交AC，就是耗时56ms多了些，要找书来学习《挑战程序设计竞赛》。
附上AC代码，编译环境Dev-C++4.9.9.2
#include <stdio.h> int f[30][30000+100]; int fun(int a,int b){ if(a>b) return a; else return b; } int main(){ int v[30],p[30],i,j,n,m; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d",&v[i],&p[i]); for(i=0;i<=m;i++) f[i][0]=0;//0元钱 for(i=0;i<=n;i++) f[0][i]=0;//挑0个 for(j=0;j<=n;j++) for(i=1;i<=m;i++) if(j<v[i]) f[i][j]=f[i-1][j]; else f[i][j]=fun(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]); printf("%d\n",f[m][n]); return 0; } 2017-4-13 21:58
10.觉得上述代码写得挺别扭的，重新搜索，找到好文http://blog.csdn.net/wumuzi520/article/details/7014559里面有比较顺手的数据生成过程，与http://blog.csdn.net/mu399/article/details/7722810刚好形成对称关系，本人更欣赏现在这篇文章的写法。认识到了《背包九讲》，最新下载https://github.com/tianyicui/pack/blob/master/V2.pdf
11.要花时间学习。
附上觉得思路还比较顺的AC代码，编译环境Dev-C++4.9.9.2
#include <stdio.h> int fun(int a,int b){ if(a>b) return a; else return b; } int v[10000+100],p[10000+100]; int f[30][30000+100]; int main(){ int n,m,i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d",&v[i],&p[i]); for(i=0;i<=n;i++) f[0][i]=0;//0种物品进行选择 for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(j<v[i]) f[i][j]=f[i-1][j]; else f[i][j]=fun(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]); printf("%d\n",f[m][n]); return 0; } 趁热打铁，顺便把二维数组化成一维数组的代码，给学习了，一开始翻了很多书都不明白，但跟踪了程序，打印出关键数据进行研究，弄懂了，附上AC的一维数组代码，编译环境Dev-C++4.9.9.2
#include <stdio.h> #include <string.h> int fun(int a,int b){ if(a>b) return a; else return b; } int v[10000+100],p[10000+100]; int f[30000+100]; int main(){ int n,m,i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d",&v[i],&p[i]); memset(f,0,sizeof(f));//初始化数组 for(i=1;i<=m;i++) for(j=n;j>=1;j--) if(j>=v[i]) f[j]=fun(f[j],f[j-v[i]]+v[i]*p[i]); printf("%d\n",f[n]); return 0; } 2017-4-17
