先看一下正确且符合时间和内存要求的答案，我模拟了牛客网的输入
let count = 0,
totalMoney = 0,
firstList = [],
secondObj = {};
`14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0`
.trim()
.split("\n")
.forEach((item, i) => {
if (i == 0) {
[totalMoney, count] = item.split(" ");
} else {
const dataList = item.split(" ");
if (dataList[2] == 0) {
firstList.push({
key: i,
price: +dataList[0],
weight: +dataList[1] * +dataList[0],
});
} else {
if (!secondObj[dataList[2]]) {
secondObj[dataList[2]] = [];
}
secondObj[dataList[2]].push({
price: +dataList[0],
weight: +dataList[1] * +dataList[0],
});
}
}
});
function able() {
let goodTwoList = [];
for (let i = 0; i < firstList.length; i++) {
const goods = firstList[i];
goodTwoList[i] = [];
goodTwoList[i].push(goods);
let childList = [...(secondObj[goods.key] || [])];
if (childList.length == 2) {
childList.push({
price: childList[0].price + childList[1].price,
weight: childList[0].weight + childList[1].weight,
});
}
childList.forEach((item) => {
const price = goods.price + item.price;
if (price <= totalMoney) {
goodTwoList[i].push({
price,
weight: goods.weight + item.weight,
});
}
});
}
const weightTwoList = [];
for (let i = 0; i < 2; i++) {
weightTwoList[i] = [];
for (let j = 0; j <= totalMoney; j++) {
weightTwoList[i][j] = 0;
}
}
for (let i = 0; i < goodTwoList.length; i++) {
let j = totalMoney;
while (j > 10) {
weightTwoList[1][j] = weightTwoList[0][j];
goodTwoList[i].forEach((item) => {
if (j >= item.price) {
weightTwoList[1][j] = Math.max(
weightTwoList[1][j],
weightTwoList[0][j - item.price] + item.weight
);
}
});
j -= 10;
}
[weightTwoList[1], weightTwoList[0]] = [
weightTwoList[0],
weightTwoList[1],
];
}
console.log(weightTwoList[0][totalMoney]);
}
able();
首先每件物品只能购买一次；购买主件时可以不买附件的，可以买一个也可以买两个。
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
400 5 1是800 2 0的附件，在这里很容易直观的看出来，但在收集数据的时候要注意索引，因为这条测试用例就算主附件关系搞错了答案也是对的，最佳选择是购买400 3 0和500 2 0
为了便于展示在简化下
10 5
8 2 0
4 5 1
3 5 1
4 3 0
5 2 0
这时候j-=10需要改成j--，j>10要改为j>0
用firstList存储主件，secondObj存储附件，weight一开始就算好，分别分：
[
{
"key": 1,
"price": 8,
"weight": 16
},
{
"key": 4,
"price": 4,
"weight": 12
},
{
"key": 5,
"price": 5,
"weight": 10
}
]
{
"1": [
{
"price": 4,
"weight": 20
},
{
"price": 3,
"weight": 15
}
]
}
因为当主件有附件时产生的结果就多于一个，所以用二维数组goodTwoList存储
if (childList.length == 2) {先把两个附件一起的情况算好，这里childList.forEach就可以统一处理，goodTwoList内容如下
[
[
{
"key": 1,
"price": 8,
"weight": 16
}
],
[
{
"key": 4,
"price": 4,
"weight": 12
}
],
[
{
"key": 5,
"price": 5,
"weight": 10
}
]
]
虽然8 2 0有两个附件，但他们组合的情况已大于总钱数，所以没有出现
初始化 weightTwoList
weightTwoList[1][j] = weightTwoList[0][j]; 这个是同步上一次的值，也代表了没有当前物品的情况。
weightTwoList[0][j - item.price] + item.weight 表示买下当前物品后，再用剩余的钱还能买到物品的期望值，买不到就是 0，因为 weightTwoList[0]的值全部初始化为 0
当执行到weightTwoList[1][j] = Math.max 就是对比最优解，先看一下 weightTwoList[1]每次存储的值:
[0, 0, 0, 0, 0, 0, 0, 0, 16, 16, 16]
[0, 0, 0, 0, 12, 12, 12, 12, 16, 16, 16]
[0, 0, 0, 0, 12, 12, 12, 12, 16, 22, 22]
也就是w[i][j] 中j就是预算为j买i 件物品的最优解，因此weightTwoList长度为 2 就可以了
因为执行了互换操作，所以最优解是weightTwoList[0][totalMoney]
想起来之间遇到过类似的题算法=>魔法硬币,j可以先从totalMoney开始，每次减去 10，虽然减少不了二维数组的长度，但是到了最后一个商品时，结果可以优先产出。
时间超出了要求
我想到了递归，
let i = 0,
count = 30,
money = 18000,
minPrice = 0;
const firstObj = {
1: {
price: 100,
weight: 3,
},
2: {
price: 400,
weight: 5,
},
5: {
price: 500,
weight: 2,
},
6: {
price: 800,
weight: 2,
},
7: {
price: 1400,
weight: 5,
},
8: {
price: 300,
weight: 5,
},
9: {
price: 1400,
weight: 3,
},
10: {
price: 500,
weight: 2,
},
11: {
price: 1800,
weight: 4,
},
14: {
price: 1400,
weight: 3,
},
15: {
price: 500,
weight: 2,
},
16: {
price: 800,
weight: 2,
},
17: {
price: 1400,
weight: 5,
},
18: {
price: 300,
weight: 4,
},
19: {
price: 1400,
weight: 3,
},
20: {
price: 500,
weight: 2,
},
21: {
price: 1800,
weight: 2,
},
25: {
price: 1400,
weight: 3,
},
25: {
price: 500,
weight: 2,
},
26: {
price: 800,
weight: 5,
},
27: {
price: 1400,
weight: 5,
},
28: {
price: 300,
weight: 5,
},
};
const secondObj = {
1: [
{
price: 1300,
weight: 5,
},
],
2: [
{
price: 1400,
weight: 2,
},
],
9: [
{
price: 400,
weight: 5,
},
{
price: 1300,
weight: 5,
},
],
20: [
{
price: 400,
weight: 5,
},
{
price: 1300,
weight: 5,
},
],
};
function able() {
const firstKeyList = Object.keys(firstObj);
let maxWeight = 0;
getCountWeight(firstObj[firstKeyList[0]], 0, 0, 0);
console.log(maxWeight);
function getCountWeight(infos, currentMoney, currentWeight, deep) {
for (let i = 0; i < 2; i++) {
currentMoney += infos.price * i;
currentWeight += infos.price * i * infos.weight;
let childList = secondObj[firstKeyList[deep]];
let dataList = [{ currentMoney, currentWeight }];
if (childList && i > 0) {
if (childList.length > 0) {
dataList.push({
currentMoney: currentMoney + childList[0].price,
currentWeight:
currentWeight + childList[0].price * childList[0].weight,
});
}
if (childList.length > 1) {
dataList.push({
currentMoney: currentMoney + childList[1].price,
currentWeight:
currentWeight + childList[1].price * childList[1].weight,
});
dataList.push({
currentMoney:
currentMoney + childList[1].price + childList[0].price,
currentWeight:
currentWeight +
childList[1].price * childList[1].weight +
childList[0].price * childList[0].weight,
});
}
}
dataList.forEach((item) => {
if (item.currentMoney <= money) {
if (deep < firstKeyList.length - 1) {
getCountWeight(
firstObj[firstKeyList[deep + 1]],
item.currentMoney,
item.currentWeight,
deep + 1
);
} else if (item.currentWeight > maxWeight) {
maxWeight = item.currentWeight;
}
}
});
}
}
}
able();
答案是正确的，但是当数据较大时，它超时了。
把主件存在firstObj里，附件存在secondObj
getCountWeight的形参分别是,infos：当前主件，currentMoney:现在用了多少钱，currentWeight:现在的期望,deep:处理到哪个主件
dataList先存下不买的情况，因为主间可能有附件，再依次处理，这里的for (let i = 0; i < 2; i++) {是多余的
Java 算法
我看了下其它答案，其中有一个 Java 算法，我把它转换为了 JS
let i = 0,
m = 5,
N = 10,
minPrice = 0;
const goods = [
{
v: 8,
p: 1600,
main: true,
a1: 1,
a2: 2,
},
{
v: 4,
p: 2000,
main: false,
a1: -1,
a2: -1,
},
{
v: 3,
p: 1500,
main: false,
a1: -1,
a2: -1,
},
{
v: 4,
p: 1200,
main: true,
a1: -1,
a2: -1,
},
{
v: 5,
p: 1000,
main: true,
a1: -1,
a2: -1,
},
];
function able() {
let dp = [];
for (let i = 0; i <= m; i++) {
dp[i] = [];
for (let j = 0; j <= N; j++) {
dp[i][j] = 0;
}
}
for (let i = 1; i <= m; i++) {
for (let j = 0; j <= N; j++) {
//情况一：什么都不选
dp[i][j] = dp[i - 1][j];
if (!goods[i - 1].main) {
//附件，直接跳过
continue;
}
//情况二：只选择主件
if (j >= goods[i - 1].v) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - goods[i - 1].v] + goods[i - 1].p
);
}
//情况三：只选择主件和第一个附件
if (
goods[i - 1].a1 != -1 &&
j >= goods[i - 1].v + goods[goods[i - 1].a1].v
) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v] +
goods[i - 1].p +
goods[goods[i - 1].a1].p
);
}
//情况四：只选择主件和第二个附件
if (
goods[i - 1].a2 != -1 &&
j >= goods[i - 1].v + goods[goods[i - 1].a2].v
) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a2].v] +
goods[i - 1].p +
goods[goods[i - 1].a2].p
);
}
//情况五：选择主件和两个附件
if (
goods[i - 1].a1 != -1 &&
goods[i - 1].a2 != -1 &&
j >=
goods[i - 1].v +
goods[goods[i - 1].a1].v +
goods[goods[i - 1].a2].v
) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][
j -
goods[i - 1].v -
goods[goods[i - 1].a1].v -
goods[goods[i - 1].a2].v
] +
goods[i - 1].p +
goods[goods[i - 1].a1].p +
goods[goods[i - 1].a2].p
);
}
}
}
console.log(dp);
}
able();
这里为了更直观的的看结果，我简化了输入，dp的存储是这样的:
[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 1200, 1200, 1200, 1200, 1600, 1600, 1600]
[0, 0, 0, 0, 1200, 1200, 1200, 1200, 1600, 2200, 2200]
一维数组代表货物。二维数组的下标代表花的钱，对应的值代表最大的期望，所以dp[m][N]就是最大的期望，这很好的控制空间，最后两个双重循环搞定，时间也没问题，这比递归的穷举好多了。
首先这个变量命名增大了阅读难度。
算法选择先初始化goods来解决先遇到附件的问题，但是主附件放到一起可以很明显的看到，dp[0]、dp[1]、dp[2]完全是重复的。
算法选择进入双重循环的时候再去处里主附件产生的不同的情况，其实增加了重复逻辑的抒写,而且有的附件加主件可能超过总钱数，没必要处理
j 没必要每次加一，因为商品的价格都是 10 的倍数
dp数组只需要两个就够了,可以看到dp[4]存储的每个数据就是当前与预算对应的最佳期望值
存储空间超出限制的算法
正所谓时间不够空间来补，看来上面的解法，我有了灵感
let count = 0,
totalMoney = 0,
firstList = [],
secondObj = {};
`14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0`
.trim()
.split("\n")
.forEach((item, i) => {
if (i == 0) {
[totalMoney, count] = item.split(" ");
} else {
const dataList = item.split(" ");
if (dataList[2] == 0) {
firstList.push({
key: i,
price: +dataList[0],
weight: +dataList[1] * +dataList[0],
});
} else {
if (!secondObj[dataList[2]]) {
secondObj[dataList[2]] = [];
}
secondObj[dataList[2]].push({
price: +dataList[0],
weight: +dataList[1] * +dataList[0],
});
}
}
});
function able() {
let goodTwoList = [];
for (let i = 0; i < firstList.length; i++) {
const goods = firstList[i];
goodTwoList[i] = [];
goodTwoList[i].push(goods);
let childList = secondObj[goods.key] || [];
if (childList.length == 2) {
childList.push({
price: childList[0].price + childList[1].price,
weight: childList[0].weight + childList[1].weight,
});
}
childList.forEach((item, index) => {
const price = goods.price + item.price;
if (price <= totalMoney) {
goodTwoList[i].push({
price,
weight: goods.weight + item.weight,
});
}
});
}
let wayList = [],
maxWeight = 0,
baseLength = 0;
for (let i = 0; i < goodTwoList.length; i++) {
let tempList = [...goodTwoList[i]];
goodTwoList[i].forEach((goods) => {
wayList.forEach((item) =>
tempList.push({
price: item.price + goods.price,
weight: item.weight + goods.weight,
})
);
});
tempList = tempList.filter((item) => {
if (item.price <= totalMoney) {
if (item.weight > maxWeight) {
maxWeight = item.weight;
}
return true;
}
});
wayList = [...wayList, ...tempList];
}
console.log(maxWeight);
}
able();
其实原计划wayList = [...wayList, ...tempList];只需用把每个货物单独的情况放进去，剩下货物之间的组合只要最后一次的就好，但其实逻辑不对，算法本身还是穷举的，例如 1,2,3,4
1
1 2 12
1 2 3 12 23 123
1 2 3 4 12 23 123 14 24 34 124 234 1234
按照优化算法在 3 的时候就只有1 2 3 23 123,少了12这种情况，如果最优解产生在这里就出问题了。
其实这种算法我在一个方便买足球彩票的前端工具、前端面试用来收尾的一道算法题都用过的，就是为了要全部结果才这么写，优化失败。
