(写在开头)
emm，这一次的上机是目前来说最自闭的一次，因为，居然！只做出了一道！看来最近的学习跟刷题还是怠慢了，要加把劲了~
(正文)
第一题，用回溯法实现0-1背包。一开始直接贴了一个dfs然后稍微的剪了一下枝，然后发现无论怎么剪枝，第三第四个样例都会TLE。没办法，只好加一个限界函数，在每一次递归前加一个判断，减少递归次数，最后才把题给A了。
//限界函数
double bound(int i){
double leftw = c-cw;
double b = cv;
while(i<=n&&p[i].w<=leftw){
leftw -= p[i].w;
b += p[i].v;
i++;
}
if(i<=n){
b += p[i].v/p[i].w*leftw;
}
return b;
}
//判断
if(bound(i+1)>bestv){
backtrack(i+1);
}
第二题，工作分配问题。这题相对而言是最简单的 （因为上机的时候只做出了这道题）。只需要贴一个dfs再剪个枝就可以过了。要注意的是剪枝的一种情况：当当前的费用已经超过了当前记录的最少费用时，就可以直接结束了，因为再递归下去，费用也不会比当前记录的少。要自己注意的是，每一次更换记录要在叶子节点时才比较，而不是在每一个子节点，这样就可以减少比较的次数使程序的效率更快。
if(sum>ans){
return ;
}
第三题，自然数的拆分，这一题是看了其他大佬们的博客才领悟出来的。一开始只是单纯的把数字按顺序从后往前挪，直到只剩两个数，再加一个判断。当写完跑出来发现这个策略会少了一些拆分方法。而看完博客后使用的策略是：在保证后面的数比前面的数小的同时，使后面的数逐渐增大，并把剩余的值递归到后面。这样子既可以保证所有拆分方法都可以输出，并且也会按字典序顺序排序。
//查询函数
void search(int s,int num){
for(int i=a[num-1];i<=s;i++){ //保证后面的数不小于前面的数
if(i<n){
s-=i; //剩余的值
a[num]=i;
if(s==0) print(num);
else search(s,num+1);
s+=i;
}
}
}