AcWing 4. 多重背包问题 I-java
原题链接
简单
作者:
单箭头
,
2019-05-11 16:49:28
,
所有人可见
,
阅读 2344
java 代码
package com.company.ForTruth.ali.背包问题;
import java.util.ArrayList;
import java.util.Scanner;
/**
* Author: hszzjs
* Date: 2019/5/10 15:52
* E-mail: hushaozhe@stu.xidian.edu.cn
* 题目描述:多重背包问题I
* 有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
*/
public class 多重背包I {
/**
* 多重背包问题明显是和完全背包一样的,只是说多了一个k的限制。所以使用完全背包的未优化算法完全OK。
* 但是依旧有优化的,关于优化就可以看是往哪里优化了。基于01背包的优化,事实上就是每个物体
* 可以看做是具有库存个数的单件物品,这样就可以了。
*/
static class VW{
int s,v,w;
public VW(int v,int w,int s){
this.s=s;
this.v=v;
this.w=w;
}
}
public static void main1(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt(),V=sc.nextInt();
VW[] vw=new VW[N];
for(int i=0;i<N;i++){
vw[i]=new VW(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
//未优化
int[][] res=new int[N+1][V+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=V;j++){
if(vw[i-1].v>j) res[i][j]=res[i-1][j];
else {
for(int k=0;k*vw[i-1].v<=j && k<=vw[i-1].s;k++){
int tmp=res[i-1][j-k*vw[i-1].v]+k*vw[i-1].w;
if(tmp>res[i][j])
res[i][j]=tmp;
}
}
}
}
System.out.println(res[N][V]);
}
//基于01背包
static class VW1{
int v,w;
public VW1(int v,int w){
this.v=v;
this.w=w;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt(),V=sc.nextInt();
ArrayList<VW1> vw=new ArrayList<>();
int cnt=0;
for(int i=0;i<N;i++){
int v=sc.nextInt(),w=sc.nextInt(),s=sc.nextInt();
for (int j=0;j<s;j++){
vw.add(new VW1(v,w));
}
cnt+=s;
}
int[][] res=new int[cnt+1][V+1];
for(int i=1;i<=cnt;i++){
for(int j=V;j>0;j--){
if(vw.get(i-1).v>j) res[i][j]=res[i-1][j];
else res[i][j]=Math.max(res[i-1][j],res[i-1][j-vw.get(i-1).v]+vw.get(i-1).w);
}
}
System.out.println(res[cnt][V]);
}
}