简单的dp
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <cstring> 5 #include <cstdio> 6 using namespace std; 7 int m,n,w[3403],c[3403],f[3403][12881]; 8 int main() 9 { 10 cin >> n >> m; 11 for (int i=1;i<=n;++i) 12 cin >> w[i] >> c[i]; 13 for (int i=1;i<=n;++i) 14 for (int v=m;v>0;--v) 15 { 16 if (w[i] <= v) 17 f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]); 18 else f[i][v] = f[i-1][v]; 19 } 20 cout << f[n][m]; 21 return 0; 22 }
这样简单的dp就写完了