01背包基础

　　dp数组开的是 最大容量!!!!! 切记不要开成N

一般有两种写法  

如果不要求打印的话

滚动数组更加省内存 

初始化只要 0-s 全为0即可

 for(int i=1;i<=n;i++)
    for(int j=s;j>=v[i];j--)
      dp[j]=max(dp[j],dp[j-v[i]+w[i]);

普通01背包

初始化将dp[0][0-j]初始化为0即可

for(int i=1;i<=n;i++)
 for(int j=S;j>=0;j--)//这里切记不能把j>=0改成 j>=v[i] 因为就算放不下也要把放不下的状态传递下去
 {
     dp[i][j]=(i==1?0:dp[i-1][j]);
    if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//注意是i-1
     
 }