fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13.  
  14. 		int[][]items = {{2,4},{3,2},{4,1},{6,4},{12,4}};
  15. 		int budget = 8;
  16.  
  17. 		int maxVal = 0;
  18.         int n = items.length;
  19.         HashMap<Integer, Integer> map = new HashMap<>();
  20.         for(int[] i : items){
  21.             maxVal = Math.max(maxVal, i[0]);
  22.             map.put(i[0], map.getOrDefault(i[0], 0) + 1);
  23.         }
  24.  
  25.         int[] gain = new int[n];
  26.  
  27.         for(int i = 0; i < n; i++){
  28.             int num = items[i][0];
  29.             int count = 0;
  30.             for(int j = num; j <= maxVal; j += num){
  31.                 count += map.getOrDefault(j, 0);
  32.             }
  33.             gain[i] = count - 1;
  34.         }
  35.  
  36.         int[][][] dp = new int[n + 1][budget + 1][2];
  37.  
  38.  
  39.         for(int j = 0; j <= budget; j++){
  40.                 if(items[0][1] <= j){
  41.                     int price = items[0][1];
  42.                     if(j - price >= 0){
  43.                     dp[0][j][1] = Math.max(1 + dp[0][j - price][0] + gain[0], 1 + dp[0][j - price][1]);
  44.                     }
  45.                 }
  46.         }
  47.  
  48.         for(int i = 1; i < n; i++){
  49.             for(int j = 0; j <= budget; j++){
  50.                 int price = items[i][1]; 
  51.                 dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i - 1][j][1]);
  52.  
  53.                 int w1 = 0;
  54.                 if(j - price >= 0){
  55.                     w1 = 1 + gain[i] + dp[i][j - price][0];
  56.                 }
  57.  
  58.                 int w2 = 0;
  59.                 if(j - price >= 0){
  60.                     w2 = 1 + dp[i][j - price][1];
  61.                 }
  62.  
  63.                 dp[i][j][1] = Math.max(w1, w2);
  64.             }
  65.         }
  66.  
  67.        int ans = Math.max(dp[n - 1][budget][0], dp[n - 1][budget][1]);
  68.        System.out.print(ans);
  69. 	}
  70. }
Success #stdin #stdout 0.1s 52540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
https://ideone.com/yBjonS
language:
Java (HotSpot 12)
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!