AcWing 3. 完全背包问题-java
原题链接
简单
作者:
单箭头
,
2019-05-11 16:47:17
,
所有人可见
,
阅读 2517
Java 代码
package com.company.ForTruth.ali.背包问题;
import java.util.Scanner;
/**
* Author: hszzjs
* Date: 2019/5/10 13:41
* E-mail: hushaozhe@stu.xidian.edu.cn
* 题目描述:完全背包
* 有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
*/
public class 完全背包 {
/**
* 完全背包问题,完全是基于01背包的扩展,问题就在于完全背包的物品件数是不限制的。所以相较于前面的,就是有一个个数k>=0,
* 这样的做法时间复杂度是O(N*V)
* 所以动态规划的递推公式就是:
* dp(i,j)=Max{dp(i-1,j),dp(i,j-k*vi)+wi*k}其中k>=1
* =Max(dp(i-1,j),dp(i,j-vi-k*vi)+k*wi+wi),其中k>=0
* =Max(dp(i-1,j),dp(i+1,j-vi)+wi)
* 参考链接:https://blog.csdn.net/zhao_xinhao/article/details/77153300
* 然后完全背包问题是正序遍历。
* 明显可以看到这个优化了的,未优化,就是对于k进行遍历,
* 时间复杂度是O(N*V^2)
*/
static class VW{
int v,w;
public VW(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();
VW[] vw=new VW[N];
for(int i=0;i<N;i++){
vw[i]=new VW(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 res[i][j]=Math.max(res[i-1][j],res[i][j-vw[i-1].v]+vw[i-1].w);
// }
// }
//未优化
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++){
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]);
}
}