首页 > 代码库 > 【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(分组背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。