Knapsack algorithm with multiple constraints via /r/learnprogramming


Knapsack algorithm with multiple constraints

I'm trying to modify this code to retrieve the best 5 knapsacks that contain exactly 6 number of weights. I have the dpTable being generated here that I can use to get the BEST knapsack, but I want the top 5. Can someone just show me the next steps? I'm just not seeing it.

public void solve(Double[] valuesArray, Integer[] weightsArray , int nItems, int maxWeight) { double[][] dpTable = new double[nItems + 1][maxWeight + 1]; boolean[][] keep = new boolean[nItems][maxWeight + 1]; for (int i = 1; i <= nItems; i++) { for (int w = 1; w <= maxWeight; w++) { if (weightsArray[i - 1] > w) { dpTable[i][w] = dpTable[i - 1][w]; } else { double pYes = valuesArray[i - 1] + dpTable[i - 1][w - weightsArray[i - 1]]; double pNo = dpTable[i - 1][w]; if (pYes > pNo) { keep[i - 1][w] = true; dpTable[i][w] = pYes; } else { dpTable[i][w] = pNo; } } } } } 

Submitted July 12, 2017 at 12:48AM by Shmua123
via reddit http://ift.tt/2tGLseI

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s