【模板】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;
}

#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;
}

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())
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N];
int main() 
{
    int n, m, w, v;
    cin >> n >> m;

    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> v >> w;
        for (int j = m; j >= v; j--)
        {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }

    int ret = 0;
    for (int i = 1; i <= m; i++)
        ret = max(ret, dp[i]);

    if (dp[m] < 0)
        dp[m] = 0;
    cout << ret << endl;//价值最大
    cout << dp[m] << endl;//恰好装满价值最大
}

def 省空间解法():
    f1 = [0 for i in range(V + 1)]
    f2 = [-999999999 for i in range(V + 1)]
    f2[0] = 0

    for i in range(1, n + 1):
        for j in range(V, items[i][0]-1, -1):  # 注意这边要逆序
            f1[j] = max(f1[j], f1[j - items[i][0]] + items[i][1])
            f2[j] = max(f2[j], f2[j - items[i][0]] + items[i][1])
    print(f1[V])
    if f2[V] < 0:
        print(0)
    else:
        print(f2[V])


def 常规解法():
    # f1[i][j]表示背包容量为j时，前i个物品能放的最大价值
    # f2[i][j]表示背包容量为j时，前i个物品恰好放满时的最大价值
    f1 = [[0 for i in range(V + 1)] for j in range(n + 1)]
    f2 = [[0 for i in range(V + 1)] for j in range(n + 1)]
    for i in range(0, n + 1):
        for j in range(1, V + 1):
            f2[i][j] = -9999999
    for i in range(1, n + 1):
        for j in range(0, V + 1):
            if j >= items[i][0]:
                f1[i][j] = max(f1[i - 1][j], f1[i - 1][j - items[i][0]] + items[i][1])
                f2[i][j] = max(f2[i - 1][j], f2[i - 1][j - items[i][0]] + items[i][1])
            else:
                f1[i][j] = f1[i - 1][j]
                f2[i][j] = f2[i - 1][j]
    print(f1[n][V])
    if f2[n][V] < 0:
        print(0)
    else:
        print(f2[n][V])


if __name__ == "__main__":
    n, V = [int(x) for x in input().split()]
    items = [[0, 0]]
    for i in range(n):
        items.append([int(x) for x in input().split()])
    # n, V = 3, 5
    # items = [[0, 0],
    #          [2, 10],
    #          [4, 5],
    #          [1, 4]]
    # items.sort(key=lambda x: x[0])
    # 常规解法()
    省空间解法()

0-1背包模板，cpp

#include <bits/stdc++.h>

using namespace std;

// 背包最多装多大价值的物品
int getResult1(vector<int>& v, vector<int>& w, int V) {
    vector<int> dp(V + 1, 0);
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    return dp[V];
}

// 恰好装满背包的最大价值
int getResult2(vector<int>& v, vector<int>& w, int V) {
    vector<int> dp(V + 1, -1);
    dp[0] = 0;
    int n = v.size();

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            if (dp[j - v[i]] >= 0) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }

    return dp[V] >= 0 ? dp[V] : 0;
}

int main() {
    int n, V;
    cin >> n >> V;

    vector<int> v(n), w(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i];
    }

    cout << getResult1(v, w, V) << endl;
    cout << getResult2(v, w, V) << endl;

    return 0;
}