Advertisement
Guest User

Untitled

a guest
Feb 18th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Main {
  4. static int N,W;
  5. static int pow(int n){
  6. int res = 1;
  7. for(int i = 0; i < n ; i ++){
  8. res *= 2;
  9. }
  10. return res;
  11. }
  12. public static void main(String[] args){
  13. Scanner sc = new Scanner(System.in);
  14. N = sc.nextInt();
  15. int[] a = new int[N];
  16. int[] c = new int[N];
  17. W = sc.nextInt();
  18. for(int i = 0; i < N ; i ++){
  19. a[i] = sc.nextInt();
  20. }
  21. for(int i = 0; i < N; i ++){
  22. c[i] = sc.nextInt();
  23. }
  24. int ans = 0;
  25. ArrayList<Integer> ansList = new ArrayList<>();
  26. for(int i = 0; i < pow(N); i ++){
  27. int cost = 0;
  28. int weight = 0;
  29. ArrayList<Integer> list = new ArrayList<>();
  30. for(int j = 0; j < N; j ++){
  31. if(((i>>j) & 1) == 1){
  32. cost += c[j];
  33. weight += a[j];
  34. list.add(j+1);
  35. }
  36. }
  37. if(!(weight>W)){
  38. if(ans < cost){
  39. ansList = list;
  40. ans = cost;
  41. }
  42. }
  43. }
  44. System.out.println(ansList.size());
  45. for(int i = 0; i < ansList.size(); i++){
  46. System.out.print(ansList.get(i) + " ");
  47. }
  48. }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement