AcWing 487. 金明的预算方案
原题链接
中等
作者:
K_cccc
,
2021-12-17 10:24:34
,
所有人可见
,
阅读 267
分组背包+状态压缩
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = reader.readLine().split("\\s+");
int money = Integer.parseInt(s[0]), n = Integer.parseInt(s[1]);
//key为主产品的id,value为主产品实体,如果该主产品有对应的附产品,则会添加到其中的slaveList中
Map<Integer, MasterGoods> masterMap = new HashMap<>();
for (int i = 1; i <= n; i++) {
s = reader.readLine().split("\\s+");
int v = Integer.parseInt(s[0]), w = Integer.parseInt(s[1]), q = Integer.parseInt(s[2]);
if (q == 0) {
//该产品是个主产品
masterMap.put(i, new MasterGoods(v, v * w));
} else {
//产品是从属产品,先根据所属的主产品找到主产品,然后将其添加进去
MasterGoods master = masterMap.get(q);
master.addSlaveGoods(new SlaveGoods(v, v * w));
}
}
writer.write(String.valueOf(dynamicProgramming(money, n, masterMap)));
writer.flush();
}
private static int dynamicProgramming(int money, int n, Map<Integer, MasterGoods> masterMap) {
int[] dp = new int[money + 1];
//遍历所有主产品,分组背包,将每一个主产品分为一组,其中的每一组主附产品的搭配情况为组内的具体情况,只能选择一种
for (Map.Entry<Integer, MasterGoods> entry : masterMap.entrySet()) {
MasterGoods master = entry.getValue();
List<SlaveGoods> slaveList = master.slaveList;
//题目规定了,物品都是10元的倍数,所以j可以每次自减10
for (int j = money; j >= 0; j -= 10) {
//遍历每一种选择的情况,二进制状态压缩
for (int status = 0; status < 1 << slaveList.size(); status++) {
int v = master.v, w = master.w;
//找到具体的选择情况
for (int i = 0; i < slaveList.size(); i++) {
if (((status >> i) & 1) == 1) {
v += slaveList.get(i).v;
w += slaveList.get(i).w;
if (v > j) break;
}
}
if (j >= v) dp[j] = Math.max(dp[j], dp[j - v] + w);
}
}
}
return dp[money];
}
private static class MasterGoods {
private int v;
private int w;
private List<SlaveGoods> slaveList = new ArrayList<>();
public MasterGoods(int v, int w) {
this.v = v;
this.w = w;
}
public void addSlaveGoods(SlaveGoods slaveGoods) { this.slaveList.add(slaveGoods); }
}
private static class SlaveGoods {
private int v;
private int w;
public SlaveGoods(int v, int w) {
this.v = v;
this.w = w;
}
}
}