Chương trình C ++ để kiểm tra xem chúng ta có thể mua sản phẩm bằng số tiền đã cho hay không

Giả sử chúng ta có số N. Một người bán bánh đang bán những chiếc bánh với 40 rupee, và những chiếc bánh rán với 70 rupee mỗi chiếc. Chúng tôi phải kiểm tra xem chúng tôi có thể mua một số trong số chúng với chính xác N rupee hay không.

Vì vậy, nếu đầu vào là N =110, thì đầu ra sẽ là Đúng, vì 40 + 70 =110.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

o := false
Define a function dfs(), this will take i,
if i > n, then:
   return false
if i is same as n, then:
   return true
if dfs(i + 40), then:
   return true
return dfs(i + 70)
From the main method, do the following
n := N
o := dfs(0)
return o

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
int n;
bool o = false;

bool dfs(int i) {
   if (i > n)
      return false;
   if (i == n)
      return true;
   if (dfs(i + 40))
      return true;
   return dfs(i + 70);
}
bool solve(int N) {
   n = N;
   o = dfs(0);
   return o;
}
int main(){
   int N = 110;
   cout << solve(N) << endl;
}

Đầu vào

110

Đầu ra

1