E08【模板】背包DP 01背包

// 朴素算法 MLE #2 #10
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=3410,M=13000;
int n, m;
int v[N],w[N],f[N][M];

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) 
    scanf("%d%d",&v[i],&w[i]);  //费用，价值
    
  for(int i=1; i<=n; i++)       //枚举物品
    for(int j=1; j<=m; j++)     //枚举体积
      if(j<v[i]) f[i][j]=f[i-1][j];            
      else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
      
  printf("%d\n",f[n][m]);
}

// 滚动数组优化空间
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=3410,M=13000;
int n, m;
int v[N],w[N],f[2][M];

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) 
    scanf("%d%d",&v[i],&w[i]);  //费用，价值
    
  for(int i=1; i<=n; i++)       //枚举物品
    for(int j=1; j<=m; j++)     //枚举体积
      if(j<v[i]) f[i&1][j]=f[i-1&1][j];            
      else f[i&1][j]=max(f[i-1&1][j],f[i-1&1][j-v[i]]+w[i]);
      
  printf("%d\n",f[n&1][m]);
}

// 逆序枚举，优化空间#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=3410,M=13000;
int n, m;
int v[N],w[N],f[M];

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) 
    scanf("%d%d",&v[i],&w[i]);  //费用，价值
    
  for(int i=1; i<=n; i++)       //枚举物品
    for(int j=m; j>=v[i]; j--)  //枚举体积
      f[j]=max(f[j],f[j-v[i]]+w[i]);
      
  printf("%d\n",f[m]);
}

// 逆序枚举，优化空间
#include<bits/stdc++.h>
using namespace std;

const int M=13000;
int n,m,v,w;
int f[M];

int main(){
  scanf("%d%d",&n,&m);

  for(int i=1; i<=n; i++){  //枚举物品
    scanf("%d%d",&v,&w);    //费用 价值
    for(int j=m; j>=v; j--) //枚举体积
      f[j]=max(f[j],f[j-v]+w);    
  }
  printf("%d\n",f[m]);
}