/******************************************************************************
Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.
*******************************************************************************/
import java.util.*;
public class Main
{
public static void main(String[] args) {
int[] profit = new int[] { 60, 10, 12 };
int[] cost = new int[] { 1, 2, 3 };
int k = 5;
List<Integer> ans = getPrices(cost, profit, k);
System.out.println(ans.toString());
}
//find most profit with budget constraint k
//cost.length == profit.length
//assuming cost[i] > 0 and profit[i] > 0 for all i
public static List<Integer> getPrices(int[] cost, int[] profit, int k){
int[][][] dp = new int[cost.length+1][k+1][2];
//in third dimension the 0=profit and 1=previous index;
int[] union = new int[cost.length];
for (int i = 0; i < union.length;i++) {
union[i] = i;
}
for (int i = 0; i < dp.length;i++){
for (int j = 0;j < dp[0].length;j++){
dp[i][j][1] = -1;
if (i == 0 || j == 0){
continue;
}
if (cost[i-1] <= j && profit[i-1] + dp[i-1][j-cost[i-1]][0] > dp[i-1][j][0]){
dp[i][j][0] = profit[i-1] + dp[i-1][j-cost[i-1]][0];
dp[i][j][1] = i-1;
union[i-1] = dp[i-1][j-cost[i-1]][1];
}
else {
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = dp[i-1][j][1];
}
}
}
List<Integer> res = new ArrayList<>();
int index = dp[cost.length][k][1];
while (index != -1){
res.add(profit[index]);
index = union[index];
}
return res;
}
}
