この問題はDPにより解くことができます。

\(\mathrm{dp}[i][j]\) を「 \(i\) 個目の商品までで合計 \(j\) 円にすることができるなら True、できないなら False」と定めます。このとき \(i\) 番目の商品を使うか使わないかを考えることで

\(\mathrm{dp}[i][j]=\mathrm{dp}[i-1][j] \lor \mathrm{dp}[i-1][j-C_i]\)

となることがわかります。 初期状態は \(\mathrm{dp}[0][0]\) が Ture、 \(j>0\) のときの \(\mathrm{dp}[0][j]\) が False です。

よって \(i\) の昇順にこのテーブルを計算することで \(O(NM)\) で答えを求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  
  vector<int> c(n);
  for(int i=0; i<n; i++) cin >> c[i];

  vector<vector<bool>> dp(n+1, vector<bool>(k+1));
  dp[0][0] = true;
  
  for(int i=1; i<=n; i++){
    for(int j=0; j<=k; j++){
      dp[i][j] = dp[i-1][j] || (j-c[i-1]>=0?dp[i-1][j-c[i-1]]:false);
    }
  }

  for(int i=k; i>=0; i--){
    if(dp[n][i]){
      cout << i << endl;
      break;
    }
  }
}

実装例 (Python)

N, K = map(int,input().split())
C = list(map(int,input().split()))

dp = [[False] * (K+1) for _ in range(N+1)]
dp[0][0] = True

for i in range(1, N+1):
  for j in range(K+1):
    dp[i][j] = dp[i-1][j] or (dp[i-1][j-C[i-1]] if j-C[i-1]>=0 else False)

for i in range(K, -1, -1):
  if dp[N][i]:
    print(i)
    break