fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int no[201],il[201],w,dp[201][20001],wyn[201];
  4.  
  5. int main(){
  6. 	ios_base::sync_with_stdio(0);
  7. 	cin.tie(0);
  8. 	cout.tie(0);
  9. 	int n,zm;
  10. 	cin>>n;
  11. 	for(int i=1;i<=n;i++) cin>>no[i];
  12. 	for(int i=1;i<=n;i++) cin>>il[i];
  13. 	cin>>w;
  14. 	for(int i=1;i<=n;i++){
  15. 		for(int j=1;j<=w;j++){
  16. 			dp[i][j]=dp[i-1][j];
  17. 			for(int k=1;k<=il[i];k++){
  18. 				if(j-k*no[i]>=0){
  19. 					if(dp[i-1][j-k*no[i]]==0){
  20. 						if(j%no[i]!=0) continue;
  21. 						else if(k*no[i]<j)continue; 
  22. 					}
  23. 					if(dp[i][j]!=0)dp[i][j]=min(dp[i-1][j-k*no[i]]+k,dp[i][j]);
  24. 					else dp[i][j]=dp[i-1][j-k*no[i]]+k;
  25. 				}
  26. 				else if(j-k*no[i]<0) break;
  27. 			}
  28. 		}
  29. 	}
  30.  
  31. 	cout<<dp[n][w]<<"\n";
  32. 	int k=n,l=w;
  33. 	while(dp[k][l]!=0){
  34. 		if(dp[k-1][l]==dp[k][l]) {k--; }
  35. 		else{
  36. 			for(int i=1;i<=il[k];i++){
  37. 				if(l-i*no[k]<0) break;
  38. 				if(dp[k-1][l-i*no[k]]+i==dp[k][l]){
  39. 					wyn[k]=i;
  40. 					l=l-i*no[k]; k--;
  41. 					break;
  42. 				}
  43. 			} 
  44. 		}
  45. 	}
  46. 	for(int i=1;i<=n;i++){
  47. 		cout<<wyn[i]<<' ';
  48. 	}
  49. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
3
2 3 5
2 2 1
10
stdout 
3
1 1 1
https://ideone.com/QFejYU
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!