01 背包

二维+DP(未优化)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int v[N], w[N];
int f[N][N];

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]); //读入第i个物品的体积和价值, 从第一件物品开始, 所以i从1开始

    //1. f[n,0~m] 枚举所有的状态
    //2. f[0,0~m] ----> 选 0 个物品, 体积从 0~m
    //3. 同理 f[1,0~m] ---> 选1个物品, 体积从 0~m

    // 初始化可以不写, 因为默认都是 0
    for (int i = 1; i <= n; i++)     //枚举所有物品
        for (int j = 1; j <= m; j++) //枚举所有体积
        {
            f[i][j] = f[i - 1][j]; // 子集左边--->不包含第 i 个物品,并且总体积<=j
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    //最后的答案就是 f[n][m]
    printf("%d\n", f[n][m]);
    return 0;
}

滚动数组+DP(优化版本)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int f[N], v[N], w[N];

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            // 1. 删除一维之后, 发现 f[i][j] = f[i-1][j] 变为了 f[j] = f[j] 这是一个恒等式, 因此可以直接删除
            // 2. j<v[i] 没有意义, 所以j可以从v[i] 开始遍历, 因此可以删除if
            // ① f[j] = max(f[j], f[j - v[i]] + w[i]);              //①不等价
            // ② f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);     //②直接删去一维后的结果等价于这个
            // ③ f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //③实际上需要的
            // ①和②等价, 我们的状态转移方程是③
            //! 因为 j-v[i] 是严格<=j 的(j从v[i]开始枚举),所以 j<=(j-v[i]), 因此 f[j-v[i]]比 f[j]先算
            //! 综上: 他其实是第 i 层的 j-v[i], 而不是 i-1层的, 改成从大到小枚举就可以了
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    printf("%d\n", f[m]);
    return 0;
}

JAVA

package _00_Algorithm;

import java.util.Scanner;

public class _00_01背包_优化版 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        final int N = 1010;
        int[] v = new int[N];
        int[] w = new int[N];
        int[] dp = new int[N];
        for(int i=1;i<=n;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        in.close();
        for(int i=1;i<=n;i++){
            for(int j= m;j>=v[i];j--){
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

Python

n, v = map(int, input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])

dp = [0 for i in range(v+1)]

for i in range(n):
    for j in range(v,-1,-1): # 从后往前
        if j >= goods[i][0]:
            dp[j] = max(dp[j], dp[j-goods[i][0]] + goods[i][1])

print(dp[-1])