Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int max(int a, int b)
  5. {
  6. return (a > b) ? a : b;
  7. }
  8.  
  9. int main()
  10. {
  11. int N, W, V;
  12. int c[100] = { 0 };
  13. int w[100] = { 0 };
  14. int v[100] = { 0 };
  15. int table[101][101] = { 0 };
  16. int ans[101] = { 0 };
  17. cin >> N; //輸入物品個數
  18. cin >> W; //輸入背包所能承載之重量
  19. cin >> V; //輸入背包所能承載之體積
  20. for (int i = 0; i < N; i++)
  21. {
  22. cin >> c[i]; //輸入各個物品的價值
  23. }
  24. for (int i = 0; i < N; i++)
  25. {
  26. cin >> w[i]; //輸入各個物品的重量
  27. }
  28. for (int i = 0; i < N; i++)
  29. {
  30. cin >> v[i];
  31. }
  32.  
  33. int i, j = 1, weight, volume, used[100] = { 0 };
  34. for (i = 0; i <= N; i++)
  35. {
  36. for (weight = 0;weight <= W;weight++)
  37. {
  38. for (volume = 0; volume <= V; volume++)
  39. {
  40. if (i == 0 || weight == 0 || volume == 0)
  41. {
  42. table[weight][volume] = 0;
  43. }
  44. else if (w[i - 1] <= weight && v[i - 1] <= volume)
  45. {
  46. table[weight][volume] = max(c[i - 1] + table[weight - w[i - 1]][volume - v[i - 1]], table[weight][volume]);
  47. }
  48. }
  49. }
  50. }
  51.  
  52. cout << table[W][V] << endl;;
  53.  
  54. int numbers = 0, temp = 0;
  55. weight = W;
  56. for (volume = V; volume >= 1; volume--)
  57. {
  58. if (table[weight][volume] == table[weight][volume - 1])
  59. continue;
  60. else if (table[weight][volume] > table[weight][volume - 1])
  61. {
  62. temp = table[weight][volume] - table[weight - 1][volume - 1];
  63. for (int i = N - 1; i >= 0; i--)
  64. {
  65. if (c[i] == temp)
  66. ans[i + 1] = 1;
  67. }
  68. weight--;
  69. }
  70. }
  71. for (int i = 1; i <= N; i++)
  72. {
  73. if (ans[i] == 1)
  74. numbers++;
  75. }
  76. cout << numbers << endl;
  77. cout << "(";
  78. weight = W;
  79. for (int i = 1; i <= N; i++)
  80. {
  81. if (ans[i] == 1)
  82. {
  83. cout << i;
  84. weight -= w[i - 1];
  85. for (int j = i+1; j <= N; j++)
  86. {
  87. if (ans[j] == 0)
  88. continue;
  89. else if (ans[j] != 0)
  90. {
  91. cout << ",";
  92. break;
  93. }
  94. }
  95. }
  96. }
  97. cout << ")";
  98.  
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement