完全背包
- 描述
-
直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO
- 输入
- 第一行： N 表示有多少组测试数据（N<7）。
接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000) - 输出
- 对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）
- 样例输入
-
2 1 5 2 2 2 5 2 2 5 1
- 样例输出
-
NO 1
- 上传者
完全背包问题属于背包问题的一个分支
对于这类问题的分析请看《背包问题小结》
完全背包问题动态规划的基础是
F[i]= max(f(i-m)+w,f(i))
也就是如果添加物品k 是能装满空间i的最佳方案，那么除去物品k 应该是在那个容量下的最佳方案
下面放代码
import java.util.Scanner;
public class FullPackage {
public static void main(String[] args) {
FullPackage.solution();
}
static final int MaxSize = 50005;
static int[] mypackage = new int[MaxSize];
public static void solution(){
Scanner in = new Scanner(System.in);
int groups = in.nextInt();
while(groups-- >0){
int catagories = in.nextInt();
int capability= in.nextInt();
for(int i = 0 ; i < MaxSize;i++){
mypackage[i] =-1000000;
}
mypackage[0]=0;
while(catagories-- >0){
int weight = in.nextInt();
int value = in.nextInt();
for(int i = weight;i<=capability;i++){
mypackage[i]=(mypackage[i-weight]+value)>mypackage[i]?(mypackage[i-weight]+value):mypackage[i];
}
}
if(mypackage[capability] <0){
System.out.println("NO");
}else{
System.out.println(mypackage[capability]);
}
}
}
}
要点一
这道题和之前我做的《开心的小明》存在一个区别就是 动态规划的时候是从高到低和还是从低到高
《开心的小明》采用从高到低的策略 因为这样可以避免物品重复的问题，添加一个物品他所考虑的情况都是不包含本身的情况
本体采用从低到高是因为物品可以重复，当考虑物品k时 如果添加一个物品k 能获得空间i+m[k]下的最佳方案，那么在考虑空间i+m[k]的时候 方案里可以包含了至少一个物品K
要点二
数组初始化的时候要赋值一个负值，但是第0位应该赋值为0，这个负值的大小是有测试数据决定的。
至于这样做的原因是要保证数组能够填满，那这是为什么？因为如果我们全部初始为0，那么我们考虑这种情况，
测试数据：
1
1 50
49 1
最后结果是1 这肯定是不对的
我们回到之前动态规划的基础，我们只考虑了要让得到的价值最大，但是我们却没有考虑背包是否被完全装满，
那么我们此时需要考虑装不满是什么情况：留出的空间是小于输入的重量数据最小的数
换句话说 这样的情况在于 我们最后得到的最大情况是基于f（i） 0<i<min（物品重量） 的情况得到
所以我们可以根据背包问题的一半算法进行修改，剔除这些情况，我们在这里就用到了这种方法，上面的代码可能不能明确的体现这点，我修改了一下
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main.solution();
}
static final int MaxSize = 50005;
static int[] mypackage = new int[MaxSize];
public static void solution(){
Scanner in = new Scanner(System.in);
int groups = in.nextInt();
while(groups-- >0){
int catagories = in.nextInt();
int capability= in.nextInt();
for(int i = 0 ; i < MaxSize;i++){
mypackage[i] =-100000;
}
mypackage[0]=0;
while(catagories-- >0){
int weight = in.nextInt();
int value = in.nextInt();
for(int i = weight;i<=capability;i++){
int cache=mypackage[i-weight]+value;
if(cache > 0){
mypackage[i]=(cache)>mypackage[i]?cache:mypackage[i];
}
}
}
if(mypackage[capability] <0){
System.out.println("NO");
}else{
System.out.println(mypackage[capability]);
}
}
}
}
这里在规划之前用一个cache 先判断一下 他是否是从一个不存在的项推出来的方案，如果是的话 那么就丢掉，如果不是那就意味着这种方案存在，最后得到结果
比较这两块代码，前一个程序中初始化的赋值很难确定， 因为没有像第二项存在一个cache进行判断 那么一个负值多次累加之后也可能变成正值
比如输入数据
1
1 5
3 1
这样应该是输出NO 那么如果我们把负值定小了，比如-1，最后我们会得到结果0 而不是我们预期的NO
第二块代码用一个cache来判断，这样负值的绝对值大小只需要大于可能的输入的数的最小值的最大值，简单说就是 输入数据的上界
(ps: 吐槽下南阳的acm网站 c++能过的代码 java 不能过， 部分题目的测试数据 java的要比c++的严格很多 也奇葩很多，按照分析 第二块代码输入的负值只需要-5W 但是我二分法测试下 确定java能过的负值范围在-8W5--10w 之间，而题目推荐代码里的负值界定只有-100)