Заполнить N предметов Рюкзак (Dp) - PullRequest
0 голосов
/ 01 октября 2019

Учитывая n предметов с размером Ai, целое число m обозначает размер рюкзака. Насколько полно вы можете заполнить этот рюкзак?

Контрольный пример: {3,4,8,5} и m = 10

Фактический результат: 9 (как и ожидалось) Я прохожу почти всемаленькие тестовые случаи, но неуспешные в большом тестовом случае, может ли кто-нибудь помочь мне, где я делаю неправильно?

int solve(vector<int>&a,int M){
    int n = a.size();
   // int M = 100;
    int dp[n][M+1];
    for(int i=0;i<=M;i++){
        dp[0][i]=a[0]<=i?a[0]:0;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=M;j++){
            if(a[i]<=j){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    return dp[n-1][M];
} 
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...