【模板】01背包

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