Similar to unbounded knapsack


#1

You can create two one dimensional dp arrays, the first array is to store the maximum hits and the second array contains the last index which has done the last index.
So , the idea is similar to the unbounded knapsack + backtracking to restore the path.


#2

Hi Shubham
I have used a similar approach, but i have used 2d array
for unbounded knapsack
and then perform backtrack.
can u help where i m wrong
here is the code

public class Solution {
public int max(int a,int b)
{
if(a>b)
return a;
return b;
}
public int[] solve(int A, int[] B) {

    int n=B.length;
    int dp[][]=new int[n+1][A+1];
    for(int i=0;i<=A;i++)
    {
        dp[0][i]=-1;
    }
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=0;
    }
    for(int i=1;i<=A;i++)
    {
        if(i%B[0]==0)
        dp[1][i]=i/B[0];
        else
        dp[1][i]=-1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=A;j++)
        {
            if(B[i-1]<=j)
            {
                dp[i][j]=max(dp[i][j-B[i-1]]+1,dp[i-1][j]);
            }
            else
            dp[i][j]=dp[i-1][j];
        }
    }
    ArrayList<Integer> al=new ArrayList<>();
    int i=n;
    int j=A;
    while(i>0&&j>0)
    {
        if(B[i-1]<=j)
        {
            if(dp[i][j-B[i-1]]+1>dp[i-1][j])
            {
                j=j-B[i-1];
                al.add(0,B[i-1]);
            }
            else if(dp[i][j-B[i-1]]+1<dp[i-1][j])
            {
                i--;
            }
            else if(dp[i][j-B[i-1]]+1==dp[i-1][j])
            {
                if(i>1)
                {
                    if(B[i-1]<B[i-2])
                    {
                    j=j-B[i-1];
                    al.add(0,B[i-1]);
                    }
                    else
                    i--;
                }
                else
                {
                    j=j-B[i-1];
                    al.add(0,B[i-1]);  
                }
                
            }
        }
        else
        {
            i--;
        }
    }
    //System.out.println(al.size());
    HashMap<Integer,Integer> map=new HashMap<>();
    for(int i2=0;i2<n;i2++)
    {
        int key=B[i2];
        map.put(key,i2);
    }
    //System.out.println(al);
    int ans[]=new int[al.size()];
    for(int k=0;k<al.size();k++)
    {
        ans[k]=map.get(al.get(k));
    }
    return ans;
}

}