HDOJ-1712 ACboy needs your help

2380 단어
이 문제는 배낭을 나누는 문제다.상태 전이 방정식: dp[v]=max(dp[v], dp[v-h]+A[i][h]);
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int A[105][105], dp[105];

int main()
{
   // freopen("in.txt", "r", stdin);
    int n, m;

    while(cin >> n >> m)
    {
        if(n == 0 && m == 0)
            break;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            cin >> A[i][j];

        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            for(int v = m; v > 0; v--)
            for(int h  = 1; h <= m; h++)
            if(v >= h)
              dp[v] = max(dp[v], dp[v-h] + A[i][h]);

        cout << dp[m] << endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기