完全背包:
完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出:
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
同样可以转换成一维数组来表示:
伪代码如下:
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
顺序!
想必大家看出了和01背包的区别,这里的内循环是顺序的,而01背包是逆序的。
现在关键的是考虑:为何完全背包可以这么写?
在次我们先来回忆下,01背包逆序的原因?是为了是max中的两项是前一状态值,这就对了。
那么这里,我们顺序写,这里的max中的两项当然就是当前状态的值了,为何?
因为每种背包都是无限的。当我们把i从1到N循环时,f[v]表示容量为v在前i种背包时所得的价值,这里我们要添加的不是前一个背包,而是当前背包。所以我们要考虑的当然是当前状态。
http://acm.hdu.edu.cn/showproblem.php?pid=1114
import java.util.Scanner;
import java.io.BufferedInputStream;
public class Main{
Scanner scan=new Scanner(new BufferedInputStream(System.in));
int t,E,F,N;
int[] dp;
int[] v=new int[1000005];
int[] w=new int[1000005];
public static void main(String[] args){
new Main().run();
}
void run(){
t=scan.nextInt();
for(int i=1;i<=t;i++)
{
E=scan.nextInt();
F=scan.nextInt();
N=scan.nextInt();
for(int j=1;j<=N;j++)
{
v[j]=scan.nextInt();
w[j]=scan.nextInt();
}
CompletePack(E,F,N,v,w,dp);
}
}
void CompletePack(int E,int F,int N,int[] v,int[] w,int[] dp){
dp=new int[1000005];
dp[0]=0;
for(int i=1;i<dp.length;i++){
dp[i]=0x1fffffff;
}
for(int i=1;i<=N;i++)
{
for(int j=w[i];j<=F-E;j++)
{
dp[j]=Math.min(dp[j],dp[j-w[i]]+v[i]);
}
}
if(dp[F-E]<0x1fffffff)
System.out.println("The minimum amount of money in the piggy-bank is "+dp[F-E]+".");
else
System.out.println("This is impossible.");
}
}
分享到:
相关推荐
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类