W3Schools Tryit 编辑器 - W3Schools 中文教程

Python

Java

#include <stdio.h>

int values[] = {300, 200, 400, 500};
int weights[] = {2, 1, 5, 3};
int capacity = 10;
int n = 4;

int knapsackTabulation() {
    int tab[n + 1][capacity + 1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                tab[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                int includeItem = values[i - 1] + tab[i - 1][w - weights[i - 1]];
                int excludeItem = tab[i - 1][w];
                tab[i][w] = (includeItem > excludeItem) ? includeItem : excludeItem;
            } else {
                tab[i][w] = tab[i - 1][w];
            }
        }
    }

// Print the DP table
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            printf("%d ", tab[i][w]);
        }
        printf("\n");
    }

// Backtrack to find the items included
    int w = capacity;
    printf("\nItems included:");
    for (int i = n; i > 0; i--) {
        if (tab[i][w] != tab[i - 1][w]) {
            printf(" %d", i - 1);
            w -= weights[i - 1];
        }
    }
    printf("\n");

return tab[n][capacity];
}

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

//C

import java.util.ArrayList;
import java.util.List;

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

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

// Populate the DP table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    int includeItem = values[i - 1] + tab[i - 1][w - weights[i - 1]];
                    int excludeItem = tab[i - 1][w];
                    tab[i][w] = Math.max(includeItem, excludeItem);
                } else {
                    tab[i][w] = tab[i - 1][w];
                }
            }
        }

// Print the DP table
        for (int[] row : tab) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }

// Backtrack to find the items included
        List<Integer> itemsIncluded = new ArrayList<>();
        int w = capacity;
        for (int i = n; i > 0; i--) {
            if (tab[i][w] != tab[i - 1][w]) {
                itemsIncluded.add(i - 1);
                w -= weights[i - 1];
            }
        }

System.out.println("\nItems included: " + itemsIncluded);

return tab[n][capacity];
    }

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

//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]

包含的项目：[3, 2, 0]

背包中的最大值 = 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

包含的项目：3 2 0

背包中的最大值 = 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

包含的项目：[3, 2, 0]

背包中的最大值 = 1200