【模板】01背包

#include<iostream>
#include<vector>
using namespace std;
int n,V;
//无需恰好装满条件下的最大价值
void func1(vector<int>& value,vector<int>& weight)
{
    vector<int> dp(V+1); //dp[i][j]：在j容量的背包下,从前i件物品挑选，所能得到的最大价值
    dp[0]=0;
    for(int i=0;i<n;i++)
        for(int j=V;j>=weight[i];j--)
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    cout<<dp[V]<<endl;
}
//需要恰好装满条件下的最大价值
void func2(vector<int>& value,vector<int>& weight)
{
    vector<int> dp(V+1);
    dp[0]=0;//容量为0的背包，恰好装满下的价值只能为0
    for(int i=1;i<=V;i++) dp[i]=-0x3f3f3f3f;//注意初始化方式的不同
    for(int i=0;i<n;i++)
        for(int j=V;j>=weight[i];j--)
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    if(dp[V]<0) cout<<0<<endl;
    else cout<<dp[V]<<endl;
}
int main()
{
    cin>>n>>V;
    vector<int> value(n),weight(n);
    for(int i=0;i<n;i++) 
        cin>>weight[i]>>value[i];
    func1(value,weight);
    func2(value,weight);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 物品数量
        int V = sc.nextInt(); // 背包最大容量
        int[] v = new int[n + 1]; // 物品体积（1-based索引）
        int[] w = new int[n + 1]; // 物品价值（1-based索引）

        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 1. 方案1：不要求装满背包，求最大价值
        int maxUnfilled = solveUnfilled(n, V, v, w);
        // 2. 方案2：要求恰好装满背包，求最大价值（无解输出0）
        int maxFilled = solveFilled(n, V, v, w);

        System.out.println(maxUnfilled);
        System.out.println(maxFilled);
        sc.close();
    }

    /**
     * 不要求装满背包的最大价值
     * 初始状态：dp[0...V] = 0（空背包价值为0，未装满也可从0开始累积）
     */
    private static int solveUnfilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量（避免重复选同一物品）
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        return dp[V];
    }

    /**
     * 要求恰好装满背包的最大价值
     * 初始状态：dp[0] = 0（容量0恰好装满时价值为0），dp[1...V] = -∞（初始标记为无法装满）
     */
    private static int solveFilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 初始化：除容量0外，其余均设为负无穷（表示无法装满）
        for (int j = 1; j <= V; j++) {
            dp[j] = Integer.MIN_VALUE;
        }

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        // 若最终容量V仍为负无穷，说明无法装满，返回0；否则返回dp[V]
        return dp[V] < 0 ? 0 : dp[V];
    }
}

#include<iostream>
#include<cstdio>
#include<climits>

using namespace std;

const int N = 1000 + 10;

int w[N], v[N], dp1[N], dp2[N];

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
        for(int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);
        fill(dp2, dp2 + m + 1, -INT_MAX);
        dp2[0] = 0;
        for(int i = 0; i < n; i++){
            for(int j = m; j >= w[i]; j--){
                dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);
                dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i]);
            }
        }
        printf("%d\n", dp1[m]);
        if(dp2[m] < 0) printf("0\n");
        else printf("%d\n", dp2[m]);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int w[1001], v[1001], dp[1001];
int main() {
    int m, n;
    cin >> n >> m;
    int dpf[1001];
    dpf[0]=0; 
    for(int i=1;i<=m;i++){
        dpf[i]=-1;
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
    	if(w[i] > m) continue;
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            if(dpf[j-w[i]]!=-1){
                dpf[j]=max(dpf[j],dpf[j-w[i]]+v[i]);
            }
        }
    }

    cout << dp[m]<<endl;
    if(dpf[m]==-1){
        cout<<0;
    }
    else{
        cout<<dpf[m];
    }
}

n,v = map(int,input().split())
vm = []
for i in range(0,n):
    vm.append(list(map(int,input().split())))
dp = [[0 for _ in range(v+1)] for _ in range(n)]
dpp = [[-float('inf')]*(v+1) for _ in range(n)]
dpp[0][0]=0
for i in range(0,v+1):
    if vm[0][0]<=i:
        dp[0][i] = vm[0][1]
    if vm[0][0] ==i :
        dpp[0][i] = vm[0][1]
for i in range(1,n):
    for j in range(1,v+1):
        if vm[i][0]>j:
            dp[i][j] = dp[i-1][j]
            dpp[i][j] = dpp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-vm[i][0]]+vm[i][1])
            dpp[i][j] = max(dpp[i-1][j],vm[i][1]+dpp[i-1][j-vm[i][0]] if dpp[i-1][j-vm[i][0]]!=-float('inf') else -float('inf'))
        
print(dp[n-1][v])
print(dpp[n-1][v] if dpp[n-1][v]!=-float('inf') else 0)

import sys

n, V = map(int, sys.stdin.readline().split())
items = []
for line in sys.stdin:
    items.append(tuple(map(int, line.split())))

dp1 = [[0 for _ in range(V + 1)] for _ in range(n + 1)]
dp2 = [[0 for _ in range(V + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    v_i, w_i = items[i - 1]
    for j in range(0, V + 1):
        dp1[i][j] = dp1[i - 1][j]
        dp2[i][j] = dp2[i - 1][j]
        if j >= v_i:
            dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - v_i] + w_i)
            if j == v_i&nbs***bsp;dp2[i - 1][j - v_i] != 0:
                dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - v_i] + w_i)

print(dp1[n][V])
print(dp2[n][V])

#include <limits.h>
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
    return (a > b ? a : b);
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int v[n + 1], w[n + 1], dp[m + 1];
    v[0] = 0, w[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &v[i], &w[i]);
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", dp[m]);
    for (int i = 1; i <= m; i++) {
        dp[i] = INT_MIN;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    printf("%d",(dp[m]>0?dp[m]:0));
    
    return 0;
}

clc 
clear

n_v_org = input('', 's');                           % 原始 输入

n_v_org = strsplit(n_v_org, ' ');                   % 拆分

n = str2double(n_v_org{1});                         % 物体 个数

T = str2double(n_v_org{2});                         % 背包 体积

prop_list = zeros(n, 2);                            % 物体 属性

for i = 1:n

    i_prop_org = input('', 's');

    i_prop_org = strsplit(i_prop_org, ' ');         % 拆分

    prop_list(i, 1) = str2double(i_prop_org{1});    % 1 物体 体积

    prop_list(i, 2) = str2double(i_prop_org{2});    % 2 物体 价值
end

prop_list;

% n = 3;                         % 物体 个数

% T = 5;                         % 背包 体积

% prop_list = [2 10
% 4 5
% 1 4];

dp_max_value = zeros(1, T+1);                       % 价值 表
dp_max_weight_value = -inf(1, T+1);                 % 价值 表
dp_max_weight_value(1) = 0;

for i = 1:n                                         % 物体 i

    i_t = prop_list(i, 1);                          % i 物体 体积

    i_v = prop_list(i, 2);                          % i 物体 价值

    for t = T+1:-1:i_t+1                            % 总 体积 t, 注意 小于 i 物体 体积 部分 不需要 计算, 加快 运行 效率
        
        if dp_max_value(1, t) < dp_max_value(1, t - i_t) + i_v
            
            dp_max_value(1, t) = dp_max_value(1, t - i_t) + i_v;
        end
        
        if dp_max_weight_value(1, t - i_t) > -1
            if dp_max_weight_value(1, t) < dp_max_weight_value(1, t - i_t) + i_v
    
                dp_max_weight_value(1, t) = dp_max_weight_value(1, t - i_t) + i_v;
            end
        end
        
        % % 上方 代码 可以 加快 计算
        % dp_max_value(1, t) = max([dp_max_value(1, t), dp_max_value(1, t - i_t) + i_v]);
        
        % if dp_max_weight_value(1, t - i_t) > -1
        %     dp_max_weight_value(1, t) = max([dp_max_weight_value(1, t), dp_max_weight_value(1, t - i_t) + i_v]);
        % end
    end
end

fprintf('%d\n%d', max(dp_max_value), max([dp_max_weight_value(T+1), 0]))

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    
    //解决第一问
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i])  
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    // 解决第二问
    memset(dp, 0, sizeof(dp));
    for (int j = 1; j <= V; j++)
        dp[0][j] = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i] && dp[i-1][j-v[i]] != -1)  
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

// 手感真好，直接一次过了
import java.util.Scanner

fun main(args: Array<String>) {
    val read = Scanner(System.`in`)
    val n = read.nextInt()
    val V = read.nextInt()
    val arr1 = IntArray(n)
    val arr2 = IntArray(n)
    repeat(n) {
        arr1[it] = read.nextInt()
        arr2[it] = read.nextInt()
    }
    val res = fun1(V, arr1, arr2)
    println(res[0])
    println(res[1])
}

private fun fun1(
    V: Int, // 背包体积
    arr1: IntArray, // 体积数组
    arr2: IntArray  // 价值数组
): IntArray {
    // 简化为一维背包问题，下标为体积，数值为价值
    val dp = IntArray(V + 1)
    // 遍历物体
    for (i in arr1.indices) {
        val v = arr1[i]
        val w = arr2[i]
        // 从后向前遍历
        for (j in dp.lastIndex downTo v) {
            if (j == v || dp[j - v] != 0) {
                dp[j] = Math.max(dp[j], dp[j - v] + w)
            }
        }
        
    }
    val max = dp.max()!!
    return intArrayOf(max, dp.last())
}