天启AI社区

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#define MAX 100+10
using namespace std;
int n, m, v;
int map[MAX][MAX];
int dp[MAX][MAX][MAX];
int max(int a, int b) {
    return (a > b) ? a : b;
}

int main(void) {
    while (~scanf("%d%d%d", &n, &m, &v)) {
                //因为背包不要求装满
        memset(dp, 0, sizeof(dp));
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &map[i][j]);
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = v; k >= map[i][j]; k--) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]);
                    dp[i][j][k] = max(dp[i][j][k], max(dp[i - 1][j][k - map[i][j]] + map[i][j], dp[i][j - 1][k - map[i][j]] + map[i][j]));

                }
            }

        }

        printf("%d\n", dp[n][m][v]);

    }
    return 0;

}