cs325/hw3/shopping.cpp
//Used GeeksforGeeks for inspiration on this function
//This is the DP function

Used GeeksforGeeks for inspiration on this function
This is the DP function
Used GeeksforGeeks for inspiration on this function This is the DP function
int knapSackDP(int W[], int P[], int N, int M, vector<int> &items) {
    int knapsack[N + 1][M + 1];
    for(int i = 0; i <= N; i++) {
        for(int weight = 0; weight <= M; weight++) {
            if(i == 0 || weight == 0) {
                knapsack[i][weight] = 0;
            }else if(W[i - 1] <= weight) { 
                knapsack[i][weight] = max(P[i - 1] + knapsack[i - 1][weight - W[i - 1]], knapsack[i - 1][weight]);
            }else{ 
                knapsack[i][weight] = knapsack[i - 1][weight];
            }
        }
    }
    int w = M;
    int max = knapsack[N][M];
    for(int i = N; i > 0 && max > 0; i--) {
        if(max != knapsack[i-1][w]) {
            items.insert(items.begin(), i);
            max -= P[i-1];
            w -= W[i-1];
        }
    }
    return knapsack[N][M];
}
int knapSackDP ( int W [ ] , int P [ ] , int N , int M , vector < int > & items ) { int knapsack [ N + 1 ] [ M + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int weight = 0 ; weight <= M ; weight ++ ) { if ( i == 0 || weight == 0 ) { knapsack [ i ] [ weight ] = 0 ; } else if ( W [ i - 1 ] <= weight ) { knapsack [ i ] [ weight ] = max ( P [ i - 1 ] + knapsack [ i - 1 ] [ weight - W [ i - 1 ] ] , knapsack [ i - 1 ] [ weight ] ) ; } else { knapsack [ i ] [ weight ] = knapsack [ i - 1 ] [ weight ] ; } } } int w = M ; int max = knapsack [ N ] [ M ] ; for ( int i = N ; i > 0 && max > 0 ; i -- ) { if ( max != knapsack [ i - 1 ] [ w ] ) { items . insert ( items . begin ( ) , i ) ; max -= P [ i - 1 ] ; w -= W [ i - 1 ] ; } } return knapsack [ N ] [ M ] ; }
Used GeeksforGeeks for inspiration on this function
This is the DP function
Used GeeksforGeeks for inspiration on this function This is the DP function
//Initialize an array knapsack
 //These for loops will fill the array knapsack
 //If the weight or i is 0, we place a 0 in the array
 //This adds a 0 to the array
 //This checks if the ith item weight is less than the current item weight
 //This line adds the maximum between the ith value and the previous value to the array knapsack
 //If no other if statement, then the else
 //This line adds the ith items to the array knapsack
 //Set w to the maximum weight
 //Set max to the maximum value in knapsack
 //For loop runs as long as i and max aren't 0
 //If the max weight doesn't equal the previous item's weight, enter if
 //Add item to the items vector
 //items.push_back(i);
 //Decrease the max and the weight
 //Return the max at n, W
