c++ 0-1背包二维dp

#include <bits/stdc++.h>
using namespace std;

const int N=105;
const int T=1005;
int t, n;
int f[N][T];

int main(){
    memset(f, 0x00, sizeof f);
    cin>>t>>n;
    int v, w;
    for(int i=1; i<=n; ++i){
        cin>>v>>w;
        for(int j=1; j<=t; ++j){
            f[i][j]=f[i-1][j];
            if(j>=v) f[i][j]=max(f[i][j], f[i-1][j-v]+w);
        }
    }
    cout<<f[n][t]<<endl;

    return 0;
}

c++ 一维dp优化

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int f[N];
int n,t;

int main(){
    memset(f, 0x00, sizeof f);
    cin>>t>>n;
    int v, w;
    for(int i=0; i<n; ++i){
        cin>>v>>w;
        for(int j=t; j>=v; --j) f[j]=max(f[j], f[j-v]+w);
    }
    cout<<f[t]<<endl;

    return 0;
}

python 0-1背包二维dp

from typing import List
class Solution:
    def main(self, n:int, t:int, a:List[List[int]]):
        f = [[0 for _ in range(t+1)] for _ in range(n+1)] # f[i][j]表示前i个物品体积为j的最大价值
        for i in range(1, n+1):
            for j in range(1, t+1):
                f[i][j]=f[i-1][j]
                if j>=a[i-1][0]:
                    f[i][j]=max(f[i-1][j], f[i-1][j-a[i-1][0]]+a[i-1][1])
        return f[n][t]



if __name__=='__main__':
    t, n= map(int, input().split())
    a=[]
    for i in range(n): 
        a.append(list(map(int, input().split())))
    sol=Solution()
    print(sol.main(n, t, a))

python 0-1背包一维优化

from typing import List
class Solution:
    def main(self, n:int, t:int):
        f = [0 for _ in range(t+1)]
        for i in range(n):
            v, w=map(int, input().split())
            for j in range(v, t+1)[::-1]:
                f[j]=max(f[j], f[j-v]+w)
        return f[t]


if __name__=='__main__':
    t, n= map(int, input().split())
    a=[]
    sol=Solution()
    print(sol.main(n, t))