$$\color{Red}{金明的预算方案:JAVA:二维和一维优化}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。
今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。
如果要买归类为附件的物品，必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。
金明想买的东西很多，肯定会超过妈妈限定的N元。
于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。
他还从因特网上查到了每件物品的价格（都是10元的整数倍）。
他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，…，jk，则所求的总和为：
v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
输入格式
输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。
如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。
输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。
数据范围
N<32000
m<60
v<10000
输入样例：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例：
2200
1.算法细节
二进制状态版本的有依赖
这道题我们意识到物品的选取应该是选取附键会强制连带选取主件，而选到了主件就可以单独买它，而未必要买附件。从中可以看出类似分组背包的思想，而强制买附件的部分，就是来自于有依赖的背包问题。
我的有依赖的背包问题题解
主体思想
每个物品有两个属性（除是否是主副键外）：体积（钱数）和价值（重要度乘钱数）
我们可以给每个物品开一个数组和对应的变长数组。数组用来存这个物品的信息，而变长数组用来存如果它是主键，它所附属的一个个附件。
而进行dp的时候，我们在选取一个主键的情况下再进行动态规划
为什么枚举到主键才进行动态规划？
因为选附件强制带主键，是一个小情况，而枚举选一个主键选附件的情况范围更大，涵盖了选附件和它主键两个物品的情况
怎么把所有的情况枚举到？
我们选取它附件的状态有2的n次方种状态(每件物品选和不选的组合)，而状态是从0到2的n次方减一！这个是个关键，而进行位判断，自然有几个附件就移位减一次，因为不移位与1就是最后一个物品选或不选的情况。采用一个二进制的枚举策略，把状态一一枚举，能放下的情况下，进行最值判断，决定是否用当前情况更新答案f[i][j]
二刷的问题
这道题陷入了为什么不给主键开ArrayList不是更省空间？到最后意识到我们List<PII>[] servant没有开多，为空的话就代表是附件，就不会进入二进制枚举。有几个附件就有2的n次方种状态，而状态是从0到2的n次方减一！这个是个关键，而进行位判断，自然有几个附件就移位减一次，因为不移位与1就是最后一个物品选或不选的情况。
二进制枚举是2 ^ n的选择，然后进行n次移位判断，判断这个附件选不选，把情况全部判断完最佳的值赋值给f[j],如果没有物品，就不会判断，自然f[j]就是上个i-1的f[j]
为了防止之后抽取到的位置为null，我们需要最开始把主件，附件的位置都new一个Pii或者ArrayList<Pii>。
java注释版 二维代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static int N = 70, M = 32010;
static int[][] f = new int[N][M];
static int n, m;
static List<Pii>[] servant = new ArrayList[N];//主键的附件
static Pii[] master = new Pii[N];//主件
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Pii {
int v, w;
public Pii(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
m = Integer.parseInt(s1[0]);
n = Integer.parseInt(s1[1]);
//初始化主键附件
for (int i = 1; i <= n; i++) {
//主键为空
master[i] = new Pii(0, 0);
//每一个主键的所有附件都用一个链表来存
servant[i] = new ArrayList<Pii>();
}
for (int i = 1; i <= n; i++) {
String[] s2 = br.readLine().split(" ");
int v = Integer.parseInt(s2[0]);
int w = Integer.parseInt(s2[1]);
int p = Integer.parseInt(s2[2]);
if (p == 0)
master[i] = new Pii(v, w * v);
else
servant[p].add(new Pii(v, w * v));
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j];
/* 二进制枚举
/* 用二进制代表附件是否选择 00 01 10 11
* 代表不选，选第一个，选第二个，两个都选
* 而为了保证不会越界多选，只需要满足小于 1 << servent[i].size()
* */
for (int k = 0; k < 1 << servant[i].size(); k++) {
//主件的价值和数量
int v = master[i].v;
int w = master[i].w;
for (int l = 0; l < servant[i].size(); l++) {
if((k >> l & 1) == 1){
v += servant[i].get(l).v;
w += servant[i].get(l).w;
}
}
if(j >= v) f[i][j] = Math.max(f[i][j], f[i-1][j - v] + w);
}
}
}
System.out.println(f[n][m]);
}
}
java注释版 二维优化一维代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static int N = 70, M = 32010;
static int[] f = new int[M];
static int n, m;
static List<Pii>[] servant = new ArrayList[N];//主键的附件
static Pii[] master = new Pii[N];//主件
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Pii {
int v, w;
public Pii(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
m = Integer.parseInt(s1[0]);
n = Integer.parseInt(s1[1]);
//初始化主键附件
for (int i = 1; i <= n; i++) {
//主键为空
master[i] = new Pii(0, 0);
//每一个主键的所有附件都用一个链表来存
servant[i] = new ArrayList<Pii>();
}
for (int i = 1; i <= n; i++) {
String[] s2 = br.readLine().split(" ");
int v = Integer.parseInt(s2[0]);
int w = Integer.parseInt(s2[1]);
int p = Integer.parseInt(s2[2]);
if (p == 0)
master[i] = new Pii(v, w * v);
else
servant[p].add(new Pii(v, w * v));
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
/* 二进制枚举
/* 用二进制代表附件是否选择 00 01 10 11
* 代表不选，选第一个，选第二个，两个都选
* 而为了保证不会越界多选，只需要满足小于 1 << servent[i].size()
* */
for (int k = 0; k < 1 << servant[i].size(); k++) {
//主件的价值和数量
int v = master[i].v;
int w = master[i].w;
for (int l = 0; l < servant[i].size(); l++) {
if((k >> l & 1) == 1){
v += servant[i].get(l).v;
w += servant[i].get(l).w;
}
}
if(j >= v) f[j] = Math.max(f[j], f[j - v] + w);
}
}
}
System.out.println(f[m]);
}
}
