Java knapsack med en liten twist
Jag jobbar eller studerar ej till utvecklare utan har fått en nytt uppdrag som teamleader för ett team med utvecklare och därför försöker jag lära mig/kunna lite programmering för att bättre förstå vad dom gör.
just nu gör jag en knapsack med en twist.,våran kapacitet är 1000, och det finns inget värde på "sakerna" utan det handlar endast om vikt.
Dessa 5 "saker" scannas in från datorn.
Twisten är att vi vill/kan gå över våran kapacitet 1000 om vikterna tex skulle se ut såhär.
input = 500,495,505,100,200.
så vill vi att programmet ska välja 500 och 505 = 105 istället för 495 och 500 995 även om antalet från 1000 är samma.
Jag är nästan klar men jag har ett problem kvar och det är när jag skriver in input 500,600,700,800,5 så väljer programmet 1105 istället för 1100 som den borde göra.
När jag pratade med en kollega sa han att jag behövde en till metod "ReversedKnapsack" som ni kan se i programmet nedan för att få det att funka.
Detta skrev han som förklaring " similar to knapsack method, but the solution must be as small as possible and must be bigger than min variable"
Jag förstod inte vad han menade och jag hann ej fråga han innan han tog helg och jag vill inte störa honom med sånt här utanför jobbet då de har en helt annan kultur kring jobb än oss svenskar.
Så därför kollar jag om ni kanske har några ideer vad han menade och kanske har några förslag på hur det skulle kunna se ut?
package kapsackidone;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
public class Kapsack {
public static void main(String[] args) throws Exception {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
int [] wt=new int[5];
int W = 1000;
System.out.println("Enter Weight 5 weights");
for(int i=0; i<5; i++)
{
wt[i]=Integer.parseInt(reader.readLine());
}
int bestClassicSolution = knapsack(wt, W);
int differenceAgainstMaxWeight = W - bestClassicSolution;
int newMaxWeight = W + differenceAgainstMaxWeight;
int bestMaxSolution = reversedKnapsack(wt, newMaxWeight, W);
int differenceAgainstWeightAboveW = W - bestMaxSolution;
if (differenceAgainstWeightAboveW <= differenceAgainstMaxWeight){
System.out.println(bestMaxSolution);
} else {
System.out.println(bestClassicSolution);
}
}
//similar to knapsack method, but the solution must be as small as possible and must be bigger than min variable
// Det är alltså här i metoden under som min kollega säger att jag behöver vilkoren över för att få det att fungera.
// suttit med detta i 2 dagar nu och får det fortf inte att fungera och är ju som sagt en novis...
// all typ av hjälp upskattas.
public static int reversedKnapsack(int wt[], int W, int min) {
int N = wt.length;
int[][] V = new int[N + 1][W + 1];
for (int item=1;item<=N;item++){
for (int weight=1;weight<=W;weight++){
if(wt[item-1] > weight)
{
V[item][weight] = V[item-1][weight];
}
else if((weight - V[item-1][weight]) < (weight - (V[item-1][weight - wt[item-1]] + wt[item-1])))
{
V[item][weight] = V[item-1][weight];
}
else
{
V[item][weight] = V[item-1][weight - wt[item-1]] + wt[item-1];
}
}
}
return min;
}
public static int knapsack(int wt[], int W) {
int N = wt.length; // Get the total number of items. Could be wt.length or val.length. Doesn't matter
int[][] V = new int[N + 1][W + 1]; //Create a matrix. Items are in rows and weight at in columns +1 on each side
for (int item=1;item<=N;item++){
//Let's fill the values row by row
for (int weight=1;weight<=W;weight++){
if(wt[item-1] > weight)
{
V[item][weight] = V[item-1][weight];
}
else if((weight - V[item-1][weight]) < (weight - (V[item-1][weight - wt[item-1]] + wt[item-1])))
{
V[item][weight] = V[item-1][weight];
}
else
{
V[item][weight] = V[item-1][weight - wt[item-1]] + wt[item-1];
}
}
}
return V[N][W];
}
}
