louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=20134

題目大意:  給不同商品，每個商品都有m單位，獲利。問m單位最大獲利。

思路:  同個商品不能重複取(比如3單位，不能取1單位+2單位同樣商品)，那枚舉所有可能，並記憶化搜索。

大致上分2種，可以取這個商品或不取。id式商品代號，rem是剩餘容量。

代碼:  

#include <bits/stdc++.h>    
#define N 105    
using namespace std;    
  
int k, m;  
int cost[N][N], dp[N][N];  
  
int dfs(int id, int rem){  
    if(rem <= 0 || id >= k) return 0;  
    if(dp[id][rem] != -1) return dp[id][rem];  
    int res = 0;  
    for(int i = rem; i >= 0; --i){  
        for(int ni = id+1; ni <= k; ++ni){  
            res = max(res, cost[id][i] + dfs(ni, rem-i));  
        }  
    }  
    return dp[id][rem]=res;  
}  
  
int main()    
{    
    while(cin >> k >> m){  
        memset(dp, -1, sizeof dp);  
        for(int i = 0; i < k; ++i){  
            for(int j = 1; j <= m; ++j){  
                cin >> cost[i][j];  
            }      
        }  
        cout << dfs(0, m) << endl;  
    }  
    return 0;    
}