AcWing 7. 混合背包问题—Java实现
原题链接
中等
作者:
FUZZ
,
2019-08-25 16:39:49
,
所有人可见
,
阅读 1537
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 V = sc.nextInt(); // 背包总容量
int[] dp = new int[V + 1];
for(int i = 0; i < N; i++){
int v = sc.nextInt(); // 体积
int w = sc.nextInt(); // 价值
int s = sc.nextInt(); // 数量
if(s == 0){
// 完全背包问题
for(int j = v; j <= V; j++){
dp[j] = Math.max(dp[j], dp[j - v] + w);
}
}else{
// 多重背包问题,01背包是多重背包的特例,可以一并处理
s = Math.abs(s);
for(int j = 1; s >= j; s -= j, j *= 2){
for(int k = V; k >= j * v; k--){
dp[k] = Math.max(dp[k], dp[k - j * v] + j * w);
}
}
if(s > 0){
for(int j = V; j >= s * v; j--){
dp[j] = Math.max(dp[j], dp[j - s * v] + s * w);
}
}
}
}
System.out.println(dp[V]);
}
}
給我想的差不多