首页 > 代码库 > 【HDU1712】ACboy needs your help(分组背包)

【HDU1712】ACboy needs your help(分组背包)

将背包九讲往后看了看,学习了一下分组背包。来做几道入门题,试试手。

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 #include <limits.h>10 #include <set>11 using namespace std;12 13 int dp[105], value[110][110];14 15 int main () {16     ios :: sync_with_stdio (false);17     int m, n;18     while (cin >> m >> n) {19         if (m == 0 && n == 0) break;20         memset (value, 0, sizeof(value));21         memset (dp, 0, sizeof(dp));22         for (int i = 1; i <= m; ++ i) {23             for (int j = 1; j <= n; ++ j) {24                 cin >> value[i][j];25             }26         }27         for (int i = 1; i <= m; ++ i) {28             for (int j = n; j >= 1; j --) {29                 for (int k = 1; k <= j; ++ k) {30                     dp[j] = max(dp[j], dp[j - k] + value[i][k]);31                 }32             }33         }34         cout << dp[n] << endl;35     }36     return 0;37 }

 

【HDU1712】ACboy needs your help(分组背包)