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

首先是最开始的二维数组的代码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//体积
    static int [] w;//价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //使用for循环精准读取count组物品数据，避免无限读取
        for(int sign = 1;sign <= count;sign++) {
            int a = in.nextInt();
            int b = in.nextInt();
            v[sign] = a;
            w[sign] = b;
        }
        //背包不满
        int ret1 = notFilled();
        //背包满
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积不超过j的最大价值，不能超过背包容量
        int [][] dp = new int[count+1][capacity+1];
        //填表
        for(int i = 1;i <= count;i++){
            //j表示当前考虑的背包容量（j），能否装得下第i个物品（v[i]）
            for(int j = 0;j <= capacity;j++){
                //挑选/不挑选i物品
                dp[i][j] = dp[i-1][j];//不挑选
                if(j >= v[i]){
                    //判断再决定是否挑选
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        return dp[count][capacity];
    }

    private static int filled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积恰好为j的最大价值，同样也不能超过背包容量
        int [][] dp = new int[count+1][capacity+1];
        //初始化，由于不选择物品怎么样也达不到超过1的容量，初始化为-1
        for(int i = 1;i <= capacity;i++){
            dp[0][i] = -1;
        }
        //填表
        for(int i = 1;i <= count;i++){
            for(int j = 0;j <= capacity;j++){
                dp[i][j] = dp[i-1][j];//不挑选
                //如果选择i物品，要确保选i之前的空间里存在最大价值（不能为-1）
                //并且还要确保有足够位置
                if(j >= v[i] && dp[i-1][j-v[i]] != -1){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        //判断下是不是-1的情况
        return dp[count][capacity] == -1 ? 0 : dp[count][capacity];
    }
}

但是这样太占空间了，我们做下空间优化，变成一个一维数组就好，并且优化常数的时间复杂度

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//体积
    static int [] w;//价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //使用for循环精准读取count组物品数据，避免无限读取
        for(int sign = 1;sign <= count;sign++) {
            int a = in.nextInt();
            int b = in.nextInt();
            v[sign] = a;
            w[sign] = b;
        }
        //背包不满
        int ret1 = notFilled();
        //背包满
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //定义dp表，dp[j]表示从前i个物品中选取体积不超过j的最大价值，不能超过背包容量
        //滚动数组优化一：一维化
        int [] dp = new int[capacity+1];
        //填表
        for(int i = 1;i <= count;i++){
            //j表示当前考虑的背包容量（j），能否装得下第i个物品（v[i]）
            //滚动数组注意点：反向填表顺序
            //并且可以再做常数级别优化，遍历到了v[i]后就不用继续判断了，因为都不符合要求了，东西背包放不下
            for(int j = capacity;j >= v[i];j--){
                //挑选/不挑选i物品
                //滚动数组优化二：不用考虑不选的情况
                if(j >= v[i]){
                    //判断再决定是否挑选
                    dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        //滚动数组优化三：直接返回值
        return dp[capacity];
    }

    private static int filled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积恰好为j的最大价值，同样也不能超过背包容量
        //滚动数组优化一：一维化
        int [] dp = new int[capacity+1];
        //初始化，由于不选择物品怎么样也达不到超过1的容量，初始化为-1
        for(int i = 1;i <= capacity;i++){
            dp[i] = -1;
        }
        //填表
        for(int i = 1;i <= count;i++){
            //滚动数组注意点：反向填表
            //并且可以再做常数级别优化，遍历到了v[i]后就不用继续判断了，因为都不符合要求了，东西背包放不下
            for(int j = capacity;j >= v[i];j--){
                //滚动数组优化二：不用考虑不选的情况
                //如果选择i物品，要确保选i之前的空间里存在最大价值（不能为-1）
                //并且还要确保有足够位置
                if(j >= v[i] && dp[j-v[i]] != -1){
                    dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        //判断下是不是-1的情况
        //滚动数组优化三：直接返回值
        return dp[capacity] == -1 ? 0 : dp[capacity];
    }
}

//背包问题总结，4种，求最大价值，且回溯物品
//1、0-1必须装满
//2、0-1可不装满
//3、可重复使用-必须装满
//4、可重复使用-可不装满

import java.util.ArrayList;
import java.util.Arrays;

public class Backpack01 {
    public static void main(String[] args) {
        int n = 5;          // 物品数量
        int V = 19;          // 背包容量
        int[] v = {12, 11, 6, 7, 8};// 物品体积
        int[] w = {6, 8, 8, 7, 10};// 物品价值

        // 0-1背包刚好装满背包的最大价值
        solution1(n, V, v, w);

        // 0-1背包不要求装满背包最大价值
        solution2(n, V, v, w);

        // 物品可重复-刚好装满背包的最大价值
        solution3(n, V, v, w);

        // 物品可重复-不要求装满背包的最大价值
        solution4(n, V, v, w);

    }

    //0-1背包问题，要求装满背包，返回最大价值，且返回选了哪些物品的索引
    public static void solution1 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] cur = new int[V + 1];
        Arrays.fill(dp, -1); // 初始化为-1，表示无法装满
        dp[0] = 0;           // 容量0刚好装满，价值0
        // 0-1背包核心循环（逆序遍历容量）
        for (int i = 0; i < n; i++) { // 遍历每个物品
            for (int j = V; j >= v[i]; j--) { // 逆序遍历容量
                // 更新dp2（要求刚好装满）
                if (dp[j - v[i]] != -1 && dp[j] < dp[j - v[i]] + w[i]) {
                    dp[j] = dp[j - v[i]] + w[i];
                    cur[j] = i;
                }
            }
        }
        if (dp[V] == -1) {
            System.out.println("无法装满背包");
        } else {
            System.out.println("刚好装满的最大价值：" + dp[V]);
            System.out.println("刚好装满的最大价值所选择的物品：");
            for (int i = V; i >= 1; ) {
                int index = cur[i] + 1;
                System.out.println("第" + index + "个物品【" + "体积：" + v[cur[i]] + "，价值：" + w[cur[i]] + "】");
                i = i - v[cur[i]];
            }
        }
    }

    //0-1背包问题，返回最大价值，不要求装满，且返回最后一个物品的索引
    public static void solution2 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] used = new int[n];
        ArrayList<Integer> list = new ArrayList<>();
        int last = solution2(n, V, v, w, used, dp);
        list.add(last);
        used[last] = 1;
        System.out.println("\n不要求装满的最大价值：" + dp[V]);

        int sum = w[last];
        for (int i = V - v[last]; i >= 1 && sum < dp[V]; ) {
            last = solution2(n, i, v, w, used, new int[i + 1]);
            list.add(last);
            used[last] = 1;
            sum += w[last];
            i = i - v[last];
        }
        System.out.println("不要求装满的最大价值所选择的物品：");
        for (Integer integer : list) {
            int index = integer + 1;
            System.out.println("第" + index + "个物品【" + "体积：" + v[integer] + "，价值：" + w[integer] + "】");
        }
    }
    private static int solution2(int n, int V, int[] v, int[] w, int[] used, int[] dp) {
        Arrays.fill(dp, 0);
        // 0-1背包核心循环（逆序遍历容量）
        int cur = 0;
        for (int i = 0; i < n; i++) { // 遍历每个物品
            if (used[i] == 1) {
                continue;
            }
            for (int j = V; j >= v[i]; j--) { // 逆序遍历容量
                // 更新dp1（不要求装满）
                if (dp[j] < dp[j - v[i]] + w[i]) {
                    dp[j] = dp[j - v[i]] + w[i];
                    cur = i;
                }
            }
        }
        return cur;
    }

    // 可重复使用物品，刚好装满背包
    public static void solution3 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] last = new int[V + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < n; j++) {
                if (i < v[j]) {
                    continue;
                }
                if (dp[i - v[j]] != -1 && dp[i] < dp[i - v[j]] + w[j]) {
                    dp[i] = dp[i - v[j]] + w[j];
                    last[i] = j;
                }
            }
        }
        if (dp[V] == -1) {
            System.out.println("\n物品可重复-无法装满背包");
        } else {
            System.out.println("\n物品可重复-刚好装满的最大价值：" + dp[V]);
            System.out.println("物品可重复-刚好装满的最大价值所选择的物品：");
            for (int i = V; i >= 1; ) {
                int index = last[i] + 1;
                System.out.println("第" + index + "种物品【" + "体积：" + v[last[i]] + "，价值：" + w[last[i]] + "】");
                i = i - v[last[i]];
            }
        }
    }

    // 可重复使用物品，不要求装满背包
    public static void solution4 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] last = new int[V + 1];
        Arrays.fill(last, -1);
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < n; j++) {
                if (i < v[j]) {
                    continue;
                }
                if (dp[i] < dp[i - v[j]] + w[j]) {
                    dp[i] = dp[i - v[j]] + w[j];
                    last[i] = j;
                }
            }
        }
        System.out.println("\n物品可重复-不要求装满的最大价值：" + dp[V]);
        System.out.println("物品可重复-不要求装满的最大价值所选择的物品：");
        for (int i = V; i >= 1; ) {
            if (last[i] == -1) {
                break;
            }
            int index = last[i] + 1;
            System.out.println("第" + index + "种物品【" + "体积：" + v[last[i]] + "，价值：" + w[last[i]] + "】");
            i = i - v[last[i]];
        }
    }
}


//输出结果
刚好装满的最大价值：18
刚好装满的最大价值所选择的物品：
第5个物品【体积：8，价值：10】
第2个物品【体积：11，价值：8】

不要求装满的最大价值：18
不要求装满的最大价值所选择的物品：
第5个物品【体积：8，价值：10】
第3个物品【体积：6，价值：8】

物品可重复-刚好装满的最大价值：23
物品可重复-刚好装满的最大价值所选择的物品：
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】
第4种物品【体积：7，价值：7】

物品可重复-不要求装满的最大价值：24
物品可重复-不要求装满的最大价值所选择的物品：
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】

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