W3Schools Tryit 编辑器 - W3Schools 中文教程

Python

Java

#include <stdio.h>

int values[] = {300, 200, 400, 500};
int weights[] = {2, 1, 5, 3};
int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack_tabulation() {
    int n = sizeof(values) / sizeof(values[0]);
    int capacity = 10;
    int tab[5][11] = {0}; // Assuming maximum capacity is 10 and number of items is 4

for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                int include_item = values[i-1] + tab[i-1][w-weights[i-1]];
                int exclude_item = tab[i-1][w];
                tab[i][w] = max(include_item, exclude_item);
            } else {
                tab[i][w] = tab[i-1][w];
            }
        }
    }

for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            printf("%d ", tab[i][j]);
        }
        printf("\n");
    }
    return tab[n][capacity];
}

int main() {
    printf("\nMaximum value in Knapsack = %d", knapsack_tabulation());
    return 0;
}

//C

public class Main {
    static int[] values = {300, 200, 400, 500};
    static int[] weights = {2, 1, 5, 3};
    static int capacity = 10;

public static int knapsack_tabulation() {
        int n = values.length;
        int[][] tab = new int[n+1][capacity+1];

for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i-1] <= w) {
                    int include_item = values[i-1] + tab[i-1][w-weights[i-1]];
                    int exclude_item = tab[i-1][w];
                    tab[i][w] = Math.max(include_item, exclude_item);
                } else {
                    tab[i][w] = tab[i-1][w];
                }
            }
        }

for (int[] row : tab) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
        return tab[n][capacity];
    }

public static void main(String[] args) {
        System.out.println("\nMaximum value in Knapsack = " + knapsack_tabulation());
    }
}

//Java

Python 结果

C 结果

Java 结果

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 300, 300, 300, 300, 300, 300, 300, 300, 300]
[0, 200, 300, 500, 500, 500, 500, 500, 500, 500, 500]
[0, 200, 300, 500, 500, 500, 600, 700, 900, 900, 900]
[0, 200, 300, 500, 700, 800, 1000, 1000, 1000, 1100, 1200]

背包中的最大值 = 1200

0 0 0 0 0 0 0 0 0 0 0
0 0 300 300 300 300 300 300 300 300 300
0 200 300 500 500 500 500 500 500 500 500
0 200 300 500 500 500 600 700 900 900 900
0 200 300 500 700 800 1000 1000 1000 1100 1200

背包中的最大值 = 1200