AcWing 2. 01背包（C++、java、python）    原题链接    简单

作者： 作者的头像   looeyWei ,  2021-05-26 17:26:20 ,  所有人可见 ,  阅读 1266

4


1

题目描述

01 背包

C++代码

int n, bag;
int v[maxn], w[maxn];
int f[maxn][maxn];

void solve(){
    read(n, bag);
    rep(i, 1, n) read(v[i], w[i]);

    rep(i, 1, n) rep(j, 1, bag){
        if(j < v[i]) f[i][j] = f[i-1][j];
        else f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
    }
    cout << f[n][bag] << endl;
}

java代码

static int n, bag;
static int[] v = new int[maxn];
static int[] w = new int[maxn];
static int[][] f = new int[maxn][maxn];

static void solve(){
    n = read.nextInt();
    bag = read.nextInt();
    for (int i = 1; i <= n; i++) {
        v[i] = read.nextInt();
        w[i] = read.nextInt();
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= bag; j++) {
            if(j < v[i]) f[i][j] = f[i-1][j];
            else f[i][j] = Math.max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    System.out.println(f[n][bag]);
}

python代码

v = [0] * maxn
w = [0] * maxn
f = [[0] * maxn for i in range(maxn)]

def solve() -> None:
    n, bag = readInt()
    for i in range(1, n+1):
        v[i], w[i] = readInt()

    for i in range(1, n+1):
        for j in range(1, bag+1):
            if(j < v[i]): f[i][j] = f[i-1][j]
            else: f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
    print(f[n][bag])

2 评论

用户头像
XYZ_08   2023-09-07 20:39         踩      回复

这个是java代码：
import java.util.Scanner;

public class Main{

public static void main(String[] args){

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();
int bag=sc.nextInt();
int[] v =new int[n+1];
int[] w=new int[n+1];
int[][] f=new int[n+1][bag+1];

for(int i=1;i<=n;i++){
  v[i] = sc.nextInt();
  w[i] = sc.nextInt();
}

for(int i=1;i<=n;i++){
  for(int j=1;j<=bag;j++){
    if(j<v[i]) f[i][j]=f[i-1][j];
    else f[i][j] =Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
  }
}

System.out.println(f[n][bag]);

}
}

用户头像
czan0307   2021-11-19 11:27         踩      回复

终于找到个python的解答了，但学完基础语法感觉还是不会这种题“简单题”。
我从哪里来~我是谁~