完全背包:
完全背包(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.");
}
}
分享到:
相关推荐
背包问题有多种变形,包括0/1背包问题、完全背包问题、多重背包问题等。 在给定的文件中,提供了一个通用的背包问题模板,使用C++语言实现。该模板可以解决各种背包问题,只需要根据问题的需求修改参数即可。 在这...
有0-1背包、完全背包、多重背包等多种类型,需要运用贪心策略或动态规划来解决。 3. **筛选法(如快速排序的划分操作)**:筛选法是一种在数组中快速选择特定元素的算法,如快速排序中的“Lomuto”或“Hoare”划分...
- **算法应用**:动态规划,解决完全背包问题,寻找最优解。 #### 2. FATE (命运) - **问题描述**:可能是基于概率的决策问题,需要在不确定性中做出最佳选择。 - **算法应用**:期望值计算,结合概率论解决决策...
2. **背包九讲.chm**:这可能是关于不同类型背包问题的深入讲解,如完全背包、多重背包、二维背包等。背包问题是动态规划的经典应用之一,在ACM竞赛中常常出现。 3. **ACM.doc**:可能是一份关于ACM竞赛的基本介绍...
6. **动态规划的应用**:常见问题如背包问题(0/1背包、完全背包、多重背包)、最长公共子序列、最短路径问题(如Floyd-Warshall算法)、矩阵链乘法等。 7. **动规思想在ACM竞赛中的应用**:ACM竞赛中,动态规划常...
2. **动态规划分类**:了解常见类型的动态规划问题,如最短路径问题(Floyd-Warshall,Dijkstra,Bellman-Ford等)、背包问题(完全背包,0-1背包,多重背包等)、图论问题(最小生成树,最长路径等)。 3. **C++...
背包问题中的二维完全背包加上几何,注意的是如何提取题意,几何的旋转性
HDU ACM讲义是一份非常经典的学术资源,涵盖了多个计算机科学竞赛编程的专题。这份讲义旨在帮助学习者深入理解并掌握ACM/ICPC(国际大学生程序设计竞赛)所涉及的各种算法和技术。通过这份资料,你可以系统地学习到...
**动态规划(DP)**是一种解决具有重叠子问题和最优子结构特征问题的有效方法,而**背包问题**是动态规划中最经典的应用之一,主要分为01背包、完全背包和多重背包等类型。 ##### 1. **01背包问题** - **定义**:...
本复习资料集合了HDU(杭州电子科技大学)的教学精华,旨在帮助学生全面掌握计算理论的核心概念,为期末考试做好充分准备。下面将详细阐述这个领域的关键知识点。 1. **计算模型**: - **图灵机**:计算理论的起源...
课件可能讲解了0-1背包、完全背包、多重背包等不同类型的背包问题,以及对应的求解策略。 4. **(HDUACM201709版_05)动态规划.ppt** - 动态规划是解决最优化问题的重要方法,课件可能会深入讲解动态规划的原理,...
背包问题是一种经典的动态规划应用,包括0-1背包、完全背包和多重背包等类型。问题通常要求在给定容量的背包中选择物品以最大化价值或最小化重量。通过构造状态数组,可以记录不同容量下背包所能达到的最大价值。...
这个算法在解决完全背包问题、0-1背包问题、数独等覆盖问题上表现出色,它巧妙地利用了数据结构,特别是双向链表的特性,来实现高效的回溯搜索。 描述中提到,DLX是“一种覆盖问题模型的算法”,这意味着它处理的...
11. **背包专题**:背包问题是一种经典的优化问题,涉及0-1背包、完全背包和多重背包等多种类型。学习背包问题有助于掌握动态规划在解决约束优化问题上的应用。 12. **hdoj_offline_2008_07_16**:这可能是某个特定...
1. 背包问题:包括0-1背包、完全背包、多重背包等,目标是使物品总价值最大或总重量最小。 2. 数学问题:如斐波那契数列、矩阵链乘、最长递增子序列等,这些问题往往可以通过定义状态和转移方程来解决。 3. 图论...
1031完全背包Piggy-Bank 6.数字金字塔(hoj 1058Number Triangles) 7.肥猫的表亲(hoj 1061Fat Cat's cousin II) 8.加建楼梯(hoj 1090The Staircases) 9.公共子序列(hoj 1227 Common Subsequence) 10.桥接的...
"(HDUACM2010版_04)动态规划.rar"是关于动态规划的经典教程,动态规划是解决优化问题的强大算法,常用于背包问题、最长公共子序列、最短路径等。 "第七部分(lecture_07)贪心算法091115.rar"讲解了贪心算法,...
但它通过设立限界函数,对搜索空间进行剪枝,避免无效的分支,通常用于解决最优化问题,如0-1背包问题。 6. **随机化算法**: 随机化算法引入了随机元素,使得算法在每次运行时可能产生不同的结果。这类算法常用于...
2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19.1 Polya . . . ....