小背包
Time Limit: 1000 MS Memory Limit: 10240 K
Total Submit: 1645(295 users) Total Accepted: 416(262 users) Rating: Special Judge: No
Description

有一个容量为m(1<=m<=4000000)的背包，有n(1<=n<=16)个物品，每个物品有体积v(1<=v<=2012)和价值w(0<=2012)，现在要你选择一些物品，使得背包所装物品的总价值最大。

Input

有多组测试数据，但是不会超过10组。

对于每组测试数据，第一行是两个整数m和n，表示背包容量的和物品个数。接下来有n行，每行有两个整数，表示一个物品的体积和价值。

输入到文件结束。

Output

对于每组测试数据，输出一行，包含一个整数，为背包能装下物品的最大价值。

Sample Input 
10 3
6 9
5 5
5 5
3 2
1 2
2 1
Sample Output 
10
3
Source
2012级新生练习赛 3
Author
黄李龙@HRBUST

注意m的问题，出题人别有用心！

#include <stdio.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)
typedef long long ll;

const int MAX_N=1e3+3;
const int MOD=1e9+7;
int dp[32195];
int w[20],v[20];
int n,m;
/// dp[i][j]:前i个物品选若干个在体积为j的背包可获得的最大价值
/// dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
int main(void){
    while((scanf("%d %d",&m,&n))!=EOF){
        if(m>=32192)    m=32192;
        /// m 为背包容量 , n为物品个数，n行体积 and 价值
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)   scanf("%d%d",&w[i],&v[i]);
        for(int i=1;i<=n;i++){
            for(int j=m;j>=w[i];j--){
               dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        printf("%d\n",dp[m]);
    }
}