宝贝，生日快乐！！！LevOJ P1439 背包九讲(1)：简单的0-1背包

思路：

对于任意一个物品，只有取或者不取两种状态，如果暴力的搜索时间复杂度是 O(n) ，是不可接受的。

因此使用动态规划的方法。设 dp[i] [j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值的最大和。

对于任意一个物品 i 有：

如果不放物品 i ，则 $dp[i][j]=dp[i-1][j]$

如果放了物品 i ，则 $dp[i][j]=dp[i-1][j-weight[i]]+value[i]$

则状态转移方程为 $dp[i][j]=max(dp[i-1][j],,dp[i-1][j-weight[i]]+value[i])$

时间复杂度 O(n*c)

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1005;

int c,n;
int w[N],v[N];
int dp[N][N];

int main(){
    while(scanf("%d%d",&c,&n)!=EOF){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=c;j++){
                if(j<w[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        cout<<dp[n][c]<<endl;
    }
    return 0;
}