先看一下正確且符合時間和內存要求的答案，我模擬了?？途W的輸入
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的附件，在這里很容易直觀的看出來，但在收集數(shù)據的時候要注意索引，因為這條測試用例就算主附件關系搞錯了答案也是對的，最佳選擇是購買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
}
]
}
因為當主件有附件時產生的結果就多于一個，所以用二維數(shù)組goodTwoList存儲
if (childList.length == 2) {先把兩個附件一起的情況算好，這里childList.forEach就可以統(tǒng)一處理，goodTwoList內容如下
[
[
{
"key": 1,
"price": 8,
"weight": 16
}
],
[
{
"key": 4,
"price": 4,
"weight": 12
}
],
[
{
"key": 5,
"price": 5,
"weight": 10
}
]
]
雖然8 2 0有兩個附件，但他們組合的情況已大于總錢數(shù)，所以沒有出現(xiàn)
初始化 weightTwoList
weightTwoList[1][j] = weightTwoList[0][j]; 這個是同步上一次的值，也代表了沒有當前物品的情況。
weightTwoList[0][j - item.price] + item.weight 表示買下當前物品后，再用剩余的錢還能買到物品的期望值，買不到就是 0，因為 weightTwoList[0]的值全部初始化為 0
當執(zhí)行到weightTwoList[1][j] = Math.max 就是對比最優(yōu)解，先看一下 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 件物品的最優(yōu)解，因此weightTwoList長度為 2 就可以了
因為執(zhí)行了互換操作，所以最優(yōu)解是weightTwoList[0][totalMoney]
想起來之間遇到過類似的題算法=>魔法硬幣,j可以先從totalMoney開始，每次減去 10，雖然減少不了二維數(shù)組的長度，但是到了最后一個商品時，結果可以優(yōu)先產出。
時間超出了要求
我想到了遞歸，
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();
答案是正確的，但是當數(shù)據較大時，它超時了。
把主件存在firstObj里，附件存在secondObj
getCountWeight的形參分別是,infos：當前主件，currentMoney:現(xiàn)在用了多少錢，currentWeight:現(xiàn)在的期望,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]
一維數(shù)組代表貨物。二維數(shù)組的下標代表花的錢，對應的值代表最大的期望，所以dp[m][N]就是最大的期望，這很好的控制空間，最后兩個雙重循環(huán)搞定，時間也沒問題，這比遞歸的窮舉好多了。
首先這個變量命名增大了閱讀難度。
算法選擇先初始化goods來解決先遇到附件的問題，但是主附件放到一起可以很明顯的看到，dp[0]、dp[1]、dp[2]完全是重復的。
算法選擇進入雙重循環(huán)的時候再去處里主附件產生的不同的情況，其實增加了重復邏輯的抒寫,而且有的附件加主件可能超過總錢數(shù)，沒必要處理
j 沒必要每次加一，因為商品的價格都是 10 的倍數(shù)
dp數(shù)組只需要兩個就夠了,可以看到dp[4]存儲的每個數(shù)據就是當前與預算對應的最佳期望值
存儲空間超出限制的算法
正所謂時間不夠空間來補，看來上面的解法，我有了靈感
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
按照優(yōu)化算法在 3 的時候就只有1 2 3 23 123,少了12這種情況，如果最優(yōu)解產生在這里就出問題了。
其實這種算法我在一個方便買足球彩票的前端工具、前端面試用來收尾的一道算法題都用過的，就是為了要全部結果才這么寫，優(yōu)化失敗。
