fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. int maxPagesSum=0;
  4. void rec(int n,int x,int*price,int*pages,int i,int priceSum,int pagesSum)
  5. {
  6. 	if(priceSum > x)
  7. 	{
  8. 		return;
  9. 	}
  10.  
  11. 	if(i == n)
  12. 	{
  13. 		if(priceSum <= x)
  14. 		{
  15. 			if(maxPagesSum < pagesSum)
  16. 			{
  17. 				maxPagesSum = pagesSum;
  18. 			}
  19. 		}
  20. 		return;
  21. 	}
  22. 	else
  23. 	{
  24. 		rec(n,x,price,pages,i+1,priceSum+price[i],pagesSum+pages[i]);
  25. 		rec(n,x,price,pages,i+1,priceSum,pagesSum);
  26. 	}
  27. }
  28.  
  29.  
  30. int main() {
  31.  
  32. 	int n,x;
  33. 	cin>>n>>x;
  34.  
  35. 	int price[n];
  36. 	for(int i=0;i<n;i++)
  37. 	{
  38. 		cin>>price[i];
  39. 	}
  40.  
  41. 	int pages[n];
  42. 	for(int i=0;i<n;i++)
  43. 	{
  44. 		cin>>pages[i];
  45. 	}
  46.  
  47. 	int DP[n+1][x+1];
  48. 	for(int i=0;i<=n;i++)
  49. 	{
  50. 		for(int j=0;j<=x;j++)
  51. 		{
  52. 			DP[i][j]=0;
  53. 		}
  54. 	}
  55.  
  56. 	for(int i=1;i<=n;i++)
  57. 	{
  58. 		for(int j=0;j<=x;j++)
  59. 		{
  60. 			if(j-price[i-1] >= 0)
  61. 			{
  62. 				DP[i][j] = max(DP[i-1][j-price[i-1]]+pages[i-1],DP[i-1][j]);
  63. 			}
  64. 			else
  65. 			{
  66. 				DP[i][j] = DP[i-1][j];
  67. 			}
  68. 		}
  69. 	}
  70.  
  71. 	cout<<DP[n][x]<<endl;
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4 10
4 8 5 3
5 12 8 1
stdout
copy 
13
https://ideone.com/3QyDaP
language:
C++14 (gcc 8.3)
created:
3 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!