$$\color{Red}{01背包问题:三种语言+原版和滚动数组优化}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入文件的第一行有两个整数 T 和 M，用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

数据范围

1 ≤ T ≤ 1000

1 ≤ M ≤ 100

输入样例：

70 3
71 100
69 1
1 2

输出样例：

3

java

import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int v[] = new int [N];
    static int w[] = new int [N];
    static int f[][] = new int [N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for(int i=1; i<=n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for(int i=1; i<=n; i++)
            for(int j=0; j<=m; j++){
                f[i][j] = f[i-1][j];
                if(v[i] <= j)
                    f[i][j] = Math.max(f[i][j], f[i-1][j - v[i]] + w[i]);
            }
        System.out.println(f[n][m]);
    }
}

java一维

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, M = 110, n, m;
    static int[] f = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String [] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[1]);
        m = Integer.parseInt(str1[0]);
        for (int i = 1; i <= n; i++) {
            String[] str2 = br.readLine().split(" ");
            int v = Integer.parseInt(str2[0]);
            int w = Integer.parseInt(str2[1]);
            for (int j = m; j >= v; j--) f[j] = Math.max(f[j], f[j - v] + w);
        }
        System.out.println(f[m]);
    }
}

python

N = 1010
v = [0] * N
w = [0] * N
f = [[0] * N for i in range(N)]

m, n = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i] = map(int, input().split())

for i in range(1, n+1):
    for j in range(1, m+1):
        f[i][j] = f[i-1][j]
        if v[i] <= j:
            f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i])

print(f[n][m])