最基础的分组背包~
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <queue> 9 #include <deque> 10 #include <queue> 11 #include <list> 12 #include <map> 13 #include <set> 14 #include <vector> 15 #include <utility> 16 #include <functional> 17 #include <fstream> 18 #include <iomanip> 19 #include <sstream> 20 #include <numeric> 21 #include <cassert> 22 #include <ctime> 23 #include <iterator> 24 const int INF = 0x3f3f3f3f; 25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; 26 using namespace std; 27 int dp[102], a[102][102]; 28 int main(void) 29 { 30 #ifndef ONLINE_JUDGE 31 freopen("in.txt", "r", stdin ); 32 #endif // ONLINE_JUDGE 33 int n,m; 34 while (~scanf("%d%d",&n,&m)&&(n||m)) 35 { 36 for (int i=1;i<=n;++i) 37 { 38 for (int j=1;j<=m;++j) scanf("%d",&a[i][j]); 39 } 40 memset(dp,0,sizeof(dp)); 41 for (int i=1;i<=n;++i) 42 { 43 for (int v=m;v>=0;--v) 44 { 45 for (int j=1;j<=v;++j) 46 { 47 dp[v]=max(dp[v],dp[v-j]+a[i][j]); 48 } 49 } 50 } 51 printf("%d ",dp[m]); 52 } 53 return 0; 54 }
没什么可说的。1Y