Skip to content

Knapsack python code beispiel

Hallo, wir haben die Lösung zu Ihrer Frage gefunden, scrollen Sie nach unten und Sie finden sie etwas weiter unten.

Beispiel 1: python 0-1 kanpsack

#Returns the maximum value that can be stored by the bagdefknapSack(W, wt, val, n):# initial conditionsif n ==0or W ==0:return0# If weight is higher than capacity then it is not includedif(wt[n-1]> W):return knapSack(W, wt, val, n-1)# return either nth item being included or notelse:returnmax(val[n-1]+ knapSack(W-wt[n-1], wt, val, n-1),
         knapSack(W, wt, val, n-1))# To test above function
val =[50,100,150,200]
wt =[8,16,32,40]
W =64
n =len(val)print(knapSack(W, wt, val, n))

Beispiel 2: Knapsack-Algorithmus in Python

# a dynamic approach# Returns the maximum value that can be stored by the bagdefknapSack(W, wt, val, n):
   K =[[0for x inrange(W +1)]for x inrange(n +1)]#Table in bottom up mannerfor i inrange(n +1):for w inrange(W +1):if i ==0or w ==0:
            K[i][w]=0elif wt[i-1]<= w:
            K[i][w]=max(val[i-1]+ K[i-1][w-wt[i-1]], K[i-1][w])else:
            K[i][w]= K[i-1][w]return K[n][W]#Main
val =[50,100,150,200]
wt =[8,16,32,40]
W =64
n =len(val)print(knapSack(W, wt, val, n))

Beispiel 3: Knapsack-Problem

// memory efficient and iterative approach to the knapsack problem

#include 
using namespace std;// n is the number of items
// w is the knapsack's capacity
int n, w;int main(){/*inputformat:
n w
value_1 cost_1
value_2 cost_2
..
value_n cost_n
*/
    cin >> n >> w;
  	vector<longlong> dp(w +1,0);for(int i =0; i < n;++i){int value, cost;
        cin >> value >> cost;for(int j = w; j >= cost;--j)
            dp[j]=max(dp[j], value + dp[j - cost]);}// the answer is dp[w]
    cout << dp[w];}

Wenn Sie sich trauen, können Sie einen Abschnitt darüber hinterlassen, was Sie diesem Aufsatz hinzufügen würden.



Nutzen Sie unsere Suchmaschine

Suche
Generic filters

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.