56. 携带矿石资源

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int c,n; // 容量 和 种类数量 
void chose(){
	vector<int>weight(n);
	vector<int>value(n);
	vector<int>nums(n);
	for(int i = 0;i < n;i++){
		cin >> weight[i];
	}
	for(int i = 0;i < n;i++){
		cin >> value[i];
	}
	for(int i = 0;i < n;i++){
		cin >> nums[i];
	}

	//标准的01背包
	vector<int>dp(c+1,0);
	for(int i = 0;i < n;i++){
		for(int j = c;j >= weight[i];j--){
			for(int k = 0;k <= nums[i] && (j - k*weight[i]) >= 0;k++){
				dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i]);
			}
			
		}
	} 
	cout << dp[c] << endl;
}
 

int main(){
	cin >> c >> n;
	chose();
	return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int C = scanner.nextInt();
        int N = scanner.nextInt();

        int[] weights = new int[N];
        int[] values = new int[N];
        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            weights[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            values[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            nums[i] = scanner.nextInt();
        }

        int[] dp = new int[C + 1];
        for(int i = 0; i < weights.length; i++) { // 遍历物品
            for(int j = C; j >= weights[i]; j--) { // 遍历背包容量
                // 以上为01背包，然后加一个遍历个数
                for (int k = 1; k <= nums[i] && (j - k * weights[i]) >= 0; k++) { // 遍历个数
                    dp[j] = Math.max(dp[j], dp[j - k * weights[i]] + k * values[i]);
                }
            }
        }
        System.out.println(dp[C]);
    }
}