ACboy needs your help HDU - 1712 （分组背包）

本文主要是介绍ACboy needs your help HDU - 1712 （分组背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ACboy needs your help

 题目链接：HDU - 1712 

题意：一共有N门课， 有M天时间；花费j天来学习第i门课，获益A[i][j]；问如何安排学习时间获益最大；

思路：每门课最多学一次，因为分多次学没有意义；分多次学，实际上就是一共学习该门课的天数和，对结果无影响，所以每门课就是一组，然后按分组背包做就好了；

#include <bits/stdc++.h>
using namespace std;
int dp[110];
int A[110][110];
int main(){int N, M;while(scanf("%d%d", &N, &M), N&&M){memset(dp, 0, sizeof(dp));for(int i=1; i<=N; i++){for(int j=1; j<=M; j++){scanf("%d", &A[i][j]);}}for(int i=1; i<=N; i++){for(int j=M; j>=0; j--){for(int k=1; k<=j; k++){dp[j]=max(dp[j], dp[j-k]+A[i][k]);}}}printf("%d\n", dp[M]);}return 0;
} 

 

这篇关于ACboy needs your help HDU - 1712 （分组背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---