携带研究材料

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取 M 和 N
    int M, N;
    cin >> M >> N;

    vector<int> costs(M);
    vector<int> values(M);

    for (int i = 0; i < M; i++) {
        cin >> costs[i];
    }
    for (int j = 0; j < M; j++) {
        cin >> values[j];
    }

    // 创建一个动态规划数组dp，初始值为0
    vector<int> dp(N + 1, 0);

    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; --j) {
            // 考虑当前研究材料选择和不选择的情况，选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
    cout << dp[N] << endl;

    return 0;
}

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;
   
int n, bagweight;// bagweight代表行李箱空间
void solve() {
    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值
    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
 
    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }
 
    for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
            // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            // 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
            // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
 
    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    while(cin >> n >> bagweight) {
        solve();    
    }
    return 0;
}

/**
 * 思路：01 背包问题，可以使用动态规划解决
 * 
 * 创建一个一维数组dp，长度为 N+1，用于存储每个行李空间下的最大总价值。
 * dp[j]表示前 i 种研究材料在给定 j 行李空间的情况下可以获得的最大总价值。
 * 初始时，dp数组的所有元素均为0。
 * 
 * 外层循环遍历每一种研究材料：
 *     内层循环从 N 递减到当前研究材料所需的空间costs[i]，
 *         表示考虑当前研究材料选择和不选择的情况。
 *         对于每个 j，更新 dp[j] 为选择当前研究材料和不选择当前研究材料中的最大值：
 *         dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i])。
 * 
 * 最终，dp[N]即为在给定 N 行李空间下可以携带的研究材料的最大总价值。
 * 输出dp[N]作为答案。
*/

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 读取 N
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int[] costs = new int[M];
        int[] values = new int[M];

        for (int i = 0; i < M; i++) {
            costs[i] = scanner.nextInt();
        }
        for (int j = 0; j < M; j++) {
            values[j] = scanner.nextInt();
        }

        // 创建一个动态规划数组dp，初始值为0
        int[] dp = new int[N + 1];

        // 外层循环遍历每个类型的研究材料
        for (int i = 0; i < M; ++i) {
            // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
            for (int j = N; j >= costs[i]; --j) {
                // 考虑当前研究材料选择和不选择的情况，选择最大值
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }

        // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
        System.out.println(dp[N]);
    }
}

'''
2D-DP: 二维dp数组
    1）dp数组含义: dp[i][j], 物品前0～i个, 背包容量为j, 所能装的最大价值
    2）递推公式: 
          针对当前物品i, 有2种状态, 取或者不取
            a) 取当前物品: 物品剩下i-1个, 背包容量剩下j-w[i], 当前价值为dp[i][j] = dp[i-1][j-w[i]]+v[i]
            b) 不取当前物品: 物品剩下i个, 背包容量剩下j, 当前价值为dp[i][j] = dp[i-1][j]
    		  最终, 取2种状态的最大价值, 即dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])
    3) 初始化: 因为i-1 -->i, j-w[i] -->j, dp数组从左上方往右下方推导的, 因此需要初始化左边界和上边界
            a) dp[0][j]: 左边界, 背包容量大于w[0],价值为v[0],反之为0
            b) dp[i][0]: 上边界, 背包容量为0,价值均为0
    4) 遍历顺序:  
            a)先物品后背包 or 先背包后物品 均可
            b)从小到大遍历
                 
                 
1D-DP: 一维dp数组,
    1）dp数组含义: dp[j]: 背包容量为j, 所能装的最大价值
    2）递推公式:  
          针对当前物品i, 有2种状态, 取或者不取。
            a) 取当前物品:   dp[j] = dp[j-w[i]] + v[i]
            b) 不取当前物品: dp[j] = dp[j]
    3) 初始化:  j--> j-w[i], 需要初始化右边界。
          dp[j] = 0
    4) 遍历顺序: 
            a) 先物品后背包
            b) 背包需要从大到小遍历:      "0/1背包", 每个物品只取1次
               如果背包从小到大遍历则变为: "完全背包", 每个物品可以取多次。
'''


class Solution():

    def knapsack_1D(self, n, capacity, weights, values):
        '''
        :param n:        物品数量
        :param capacity: 背包容量
        :param weights:  物品重量
        :param values:   物品价值
        :return:
        '''
        # 创建1维dp数组
        dp = [0] * (capacity + 1)

        # 先物品后背包 & 背包从大到小遍历, 更新dp数组
        for i in range(n):
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

        return dp[capacity]

    def knapsack_2D(self, n, capacity, weights, values):
        '''
        :param n:        物品数量
        :param capacity: 背包容量
        :param weights:  物品重量
        :param values:   物品价值
        :return:
        '''
        # 创建2维dp数组
        dp = [[0] * (capacity + 1) for _ in range(n)]

        # 初始化dp[0][j]
        for j in range(capacity + 1):
            if j >= weights[0]:
                dp[0][j] = values[0]

        # 先物品后背包 & 背包从小到大, 更新dp数组
        for i in range(1, n):
            for j in range(capacity + 1):
                if j >= weights[i]:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[n - 1][capacity]

    def get_input(self):
        # 获取输入
        n, capacity = map(int, input().split())
        weights = list(map(int, input().split()))
        values = list(map(int, input().split()))

        return n, capacity, weights, values


solution_obj = Solution()
n, capacity, weights, values = solution_obj.get_input()

print(solution_obj.knapsack_1D(n=n, capacity=capacity, weights=weights, values=values))  # 1D-dp数组
print(solution_obj.knapsack_2D(n=n, capacity=capacity, weights=weights, values=values))  # 2D-dp数组

//必须使用bufio.NewScanner解决输入，不然会超时

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	var m, n int
	fmt.Scan(&m, &n)
	materialSpaces := make([]int, m)
	inputs := bufio.NewScanner(os.Stdin)
	inputs.Scan()                             //每次读入一行
	data := strings.Split(inputs.Text(), " ") //通过空格将他们分割，并存入一个字符串切片
	for i := range data {
		val, _ := strconv.Atoi(data[i]) //将字符串转换为int
		materialSpaces[i] = val
	}
	inputs.Scan()
	materialValues := make([]int, m)
	data = strings.Split(inputs.Text(), " ") //通过空格将他们分割，并存入一个字符串切片
	for i := range data {
		val, _ := strconv.Atoi(data[i]) //将字符串转换为int
		materialValues[i] = val
	}
	dp := make([]int, n+1)
	for i := 0; i < m; i++ {
		for j := n; j >= materialSpaces[i]; j-- {
			dp[j] = max(dp[j], dp[j-materialSpaces[i]]+materialValues[i])
		}
	}
	fmt.Println(dp[n])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int M, N;
    scanf("%d %d", &M, &N);

    int* costs = (int*)malloc(M * sizeof(int));
    int* values = (int*)malloc(M * sizeof(int));

    for (int i = 0; i < M; i++) {
        scanf("%d", &costs[i]);
    }
    for (int j = 0; j < M; j++) {
        scanf("%d", &values[j]);
    }

    int* dp = (int*)malloc((N + 1) * sizeof(int));

    // 初始化dp数组为0
    for (int i = 0; i <= N; i++) {
        dp[i] = 0;
    }

    for (int i = 0; i < M; ++i) {
        // 内层循环从N递减到当前研究材料所需的空间costs[i]
        for (int j = N; j >= costs[i]; --j) {
            // 计算选择当前材料和不选择当前材料的最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    printf("%d\n", dp[N]);

    // 释放动态分配的内存
    free(costs);
    free(values);
    free(dp);

    return 0;
}