学步园

题目链接~~>

做题感悟：这题是在做周赛时接触的，一看题目感觉很简单，又一看数据没法开数组，那就只有用搜索了，果断超时。

解题思路：因为价值最多才 1e4 所以可以把价值看成背包的容量，选的时候选重量轻的，之后再从最大价值开始遍历，只要重量满足就 break ;

代码：

#include<stdio.h>
const int INF =1e9+5 ;
int w[105],v[105],dp[10005] ;
int main()
{
    int i,j,n,m ;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int sum=0 ;
        for(i=0 ;i<n ;i++)
        {
            scanf("%d%d",&w[i],&v[i]) ;
            sum+=v[i] ; // 价值上限
        }
        dp[0]=0 ;
        for(i=1 ;i<=sum ;i++)
               dp[i]=INF ;
        for(i=0 ;i<n ;i++)
          for(j=sum ;j>=v[i] ;j--)
              if(dp[j]>dp[j-v[i]]+w[i])
                      dp[j]=dp[j-v[i]]+w[i] ;
        for(j=sum ;j>=0 ;j--)
          if(dp[j]<=m)
           {
               printf("%d\n",j) ;
               break ;
           }
    }
    return 0 ;
}