题目描述
ACboy needs your help
解法：分组背包问题
输入的价值矩阵中，一行即为一个分组
#include <iostream>
#include <string.h>
#include <algorithm>using namespace std;int A[105][105];
int dp[105];int main()
{
int n, m;while(scanf("%d%d", &n, &m)==2 && (n || m)){
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d", &A[i][j]);memset(dp, 0, sizeof(dp));for(int k=1;k<=n;k++)for(int j=m;j>=0;j--)for(int i=1;i<=j;i++)dp[j] = max(dp[j], dp[j-i]+A[k][i]);printf("%d\n", dp[m]);}return 0;
}