【模板】完全背包

[编程题]【模板】完全背包

热度指数：12297 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为 $v_i$ ,价值为 $w_i$ 。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述:

第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数和，表示第i种物品的体积和价值。

输出描述:

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入

2 6
5 10
3 1

输出

10
2

示例2

输入

输出

20
0

说明

无法恰好装满背包。

示例3

输入

输出

596
189

说明

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

算法知识视频讲解

Java

牛客818227959号

下面的代码为什么是80%通过率的，没想明白

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int num = in.nextInt();
int bagW = in.nextInt();

int[] array = new int[bagW+1];
int[] array1 = new int[bagW+1];
for(int j=bagW;j>0;j--){
array1[j]=Integer.MIN_VALUE;
}
for(int i=1;i<=num;i++){
int w = in.nextInt();
int v = in.nextInt();
for(int j=bagW;j>=0;j--){
int max = array[j];
int max1 = array1[j];
for(int k=1;k*w<=j;k++){
max=Math.max(array[j-k*w]+k*v,array[j]);
max1=Math.max(array1[j-k*w]+k*v,array1[j]);
}
array[j]=max;
array1[j]=max1;
}
}
System.out.println(array[bagW]);
if(array1[bagW]<0){
array1[bagW]=0;
}
System.out.println(array1[bagW]);
}
}

发表于 2022-05-27 16:44:47 回复(0)