fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	int n;
  6. 	cin>>n;
  7. 	int a[n];
  8. 	for(int i=0; i<n; i++){
  9. 		cin>>a[i];
  10. 	}
  11. 	int s;
  12. 	cin>>s;
  13. 	int dp[s+1]={0,};
  14. 	for(int i=0; i<n; i++){
  15. 		dp[a[i]]=1;
  16. 		for(int j=a[i]+1; j<=s; j++){
  17. 			if(dp[j-a[i]]>0 or j==a[i]){
  18. 				if(dp[j]>dp[j-a[i]]+1 or dp[j]==0)
  19. 					dp[j]=dp[j-a[i]]+1;
  20.  
  21. 			}
  22. 		}
  23. 	}
  24. 	if(dp[s]==0){
  25. 		cout<<"No solution"<<endl;
  26. 	return 0;
  27. 	}
  28. 	cout<<dp[s]<<endl;
  29. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5
1 3 7 12 32
40
stdout
copy 
3
https://ideone.com/rAYsKw
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!