W3Schools Tryit 编辑器 - W3Schools 中文教程

Python

Java

#include <stdio.h>
#include <string.h>

int values[] = {300, 200, 400, 500};
int weights[] = {2, 1, 5, 3};
int memo[5][11];  // Assuming maximum capacity is 10 and number of items is 4

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack_memoization(int capacity, int n) {
    printf("knapsack_memoization(%d,%d)\n", n, capacity);
    if (memo[n][capacity] != -1) {
        printf("Using memo for (%d,%d)\n", n, capacity);
        return memo[n][capacity];
    }
    
    int result;
    if (n == 0 || capacity == 0)
        result = 0;
    else if (weights[n - 1] > capacity)
        result = knapsack_memoization(capacity, n - 1);
    else {
        int include_item = values[n - 1] + knapsack_memoization(capacity - weights[n - 1], n - 1);
        int exclude_item = knapsack_memoization(capacity, n - 1);
        result = max(include_item, exclude_item);
    }

memo[n][capacity] = result;
    return result;
}

int main() {
    memset(memo, -1, sizeof(memo));
    int n = sizeof(values) / sizeof(values[0]);
    int capacity = 10;
    printf("\nMaximum value in Knapsack = %d", knapsack_memoization(capacity, n));
    return 0;
}

//C

public class Main {
    static int[] values = {300, 200, 400, 500};
    static int[] weights = {2, 1, 5, 3};
    static Integer[][] memo = new Integer[5][11]; // Assuming maximum capacity is 10 and number of items is 4

public static int knapsack_memoization(int capacity, int n) {
        System.out.println("knapsack_memoization(" + n + "," + capacity + ")");
        if (memo[n][capacity] != null) {
            System.out.println("Using memo for (" + n + "," + capacity + ")");
            return memo[n][capacity];
        }
        
        int result;
        if (n == 0 || capacity == 0)
            result = 0;
        else if (weights[n - 1] > capacity)
            result = knapsack_memoization(capacity, n - 1);
        else {
            int include_item = values[n - 1] + knapsack_memoization(capacity - weights[n - 1], n - 1);
            int exclude_item = knapsack_memoization(capacity, n - 1);
            result = Math.max(include_item, exclude_item);
        }

memo[n][capacity] = result;
        return result;
    }

public static void main(String[] args) {
        int n = values.length;
        int capacity = 10;
        System.out.println("\nMaximum value in Knapsack = " + knapsack_memoization(capacity, n));
    }
}

//Java

Python 结果

C 结果

Java 结果

knapsack_memoization(4,10)
knapsack_memoization(3,7)
knapsack_memoization(2,2)
knapsack_memoization(1,1)
knapsack_memoization(0,1)
knapsack_memoization(1,2)
knapsack_memoization(0,0)
knapsack_memoization(0,2)
knapsack_memoization(2,7)
knapsack_memoization(1,6)
knapsack_memoization(0,4)
knapsack_memoization(0,6)
knapsack_memoization(1,7)
knapsack_memoization(0,5)
knapsack_memoization(0,7)
knapsack_memoization(3,10)
knapsack_memoization(2,5)
knapsack_memoization(1,4)
knapsack_memoization(0,2)
使用 memo for (0,2)
knapsack_memoization(0,4)
使用 memo for (0,4)
knapsack_memoization(1,5)
knapsack_memoization(0,3)
knapsack_memoization(0,5)
使用 memo for (0,5)
knapsack_memoization(2,10)
knapsack_memoization(1,9)
knapsack_memoization(0,7)
使用 memo for (0,7)
knapsack_memoization(0,9)
knapsack_memoization(1,10)
knapsack_memoization(0,8)
knapsack_memoization(0,10)

背包中的最大值为 1200