Исплата са најмање новчића

Pitanje ili opis problema

Cao, ja imam jedno resenje dp problema za koje mislim da je okej, medjutim padaju mi dva test primera. Zadtak jos nije resio pa je mozda do test primera. Naime, nije receno sta da se ispise ako ne postoji resenje. Ovo je moj kod:

#include<bits/stdc++.h>

using namespace std;

int n,s;
int a[1050];
int dp[1050][1050];

int main(){
cin>>s>>n;
for(int i=0; i<n; i++)
    cin>>a[i];

for(int i=0; i<n; i++)
    for(int j=1; j<=s; j++)
       dp[i][j]=-1;
       
for(int i=0; i<=s; i++)
    if(i%a[0]==0)
        dp[0][i]= i/a[0];

for(int i=1; i<n; i++){
    int j=1;
    while(a[i]>j){
        dp[i][j]= dp[i-1][j];
        j++;
    }

    for(; j<=s; j++){
        if((dp[i-1][j]==-1) && (dp[i][j-a[i]]==-1))
            dp[i][j]=-1;
        else if(dp[i-1][j]==-1){
            dp[i][j]=dp[i][j-a[i]]+1;
        }
        else if(dp[i][j-a[i]]==-1){
            dp[i][j]=dp[i-1][j];
        }
        else
            dp[i][j]= min(dp[i][j-a[i]]+1, dp[i-1][j]);
    }
}

cout<<dp[n-1][s]<<"\n";

return 0;
}

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/isplata_sa_najmanje_novcica#solution

Samo za 9. test primer nema resenje i onda sam samo probao u slucaju kada nema resenja da ispise -1 i dobio sam OK. Ideja je samo da je dp[i][j] minimalna broj novcica tako da koristis prvih i novcica, a da suma bude jednaka j. Evo ga moj kod:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);             
  int s, n;
  cin >> s >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  vector<vector<int>> dp(n, vector<int>(10000, INF));
  for (int i = 0; i < n; i++) {
    dp[i][0] = 0;
    for (int j = 1; j <= s; j++) {
      if (a[i] > j) {
        if (i == 0) continue;
        else {
          dp[i][j] = dp[i - 1][j];
          continue;
        }
      }
      if (i == 0) {
        dp[i][j] = dp[i][j - a[i]] + 1;
      } else {
        dp[i][j] = min(dp[i - 1][j - a[i]] + 1, dp[i][j - a[i]] + 1); 
      }
    }
  }                          
  int ans = INF;
  for (int i = 0; i < n; i++) {
    ans = min(ans, dp[i][s]);
  }
  if (ans != INF) cout << ans << '\n';
  else cout << -1 << '\n';
  return 0;
}
1 Like

Pa to je bila isto moja ideja, medjutim nikako mi nije jasno zasto mi ne prolaze 8 i 10. test primeri, cak i ako gledam minimum od svih dp[i][s] za svako i (mada ne vidim zasto je taj deo nepohodan jer mi treba da cuvamo ukupan minimum u dp[n-1][s]).