首页 > 试题广场 >

购物单

[编程题]购物单

热度指数：483945 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
$\hspace{23pt}\bullet\,$ 主件可以没有附件，至多有 $2$ 个附件。附件不再有从属于自己的附件。
$\hspace{23pt}\bullet\,$ 若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。

$\hspace{15pt}$ 王强查到了 $m$ 件物品的价格，而他只有 $n$ 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数 $1 \sim 5$ 表示。他希望在不超过预算的前提下，使满意度最大。

$\hspace{15pt}$ 满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第 $i$ 件物品的价格为 $v_i$ ，重要度为 $w_i$ ；若共选中 $k$ 件物品，编号为 $j_1,j_2,\dots,j_k$ ，则满意度计算为： $\sum\limits_{t=1}^{k} v_{j_t} \times w_{j_t} = v_{j_1} w_{j_1} + v_{j_2} w_{j_2} + \dots + v_{j_k} w_{j_k}$

$\hspace{15pt}$ 请你帮助王强计算可获得的最大的满意度。

输入描述:

第一行输入两个整数  代表预算、查询到的物品总数。
此后  行，第  行输入三个整数  代表第  件物品的价格、重要度、主件编号。特别地， 代表该物品为主件，否则表示该附件从属于主件 。编号即输入顺序，从  开始。

特别地，保证全部物品的价格  均为  的倍数；且每个主件的附件数不超过  个。

输出描述:

在一行上输出一个整数，代表王强可获得的最大满意度。

示例1

输入

输出

说明

在这个样例中，第三、四、五件物品为主件，第一、二件物品为第五件物品的附件。这就意味着，如果购买了第一件物品或第二件物品，则必须购买第五件物品；但是特别地，如果同时购买了第一件物品和第二件物品，则只需要购买一次第五件物品。
我们可以证明，购买一、二、五件商品，获得的满意度最大，为 。

示例2

输入

输出

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-05-15 更新题面，新增几组hack数据（暂未进行重测）。
2. 2024-12-13 更新题面。

算法知识视频讲解

JavaScript Node

不秃顶的程序员

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
function maxSatisfaction(n, m, items) {
    // 分离主件和附件
    const main = [],
        attach = {};
    items.forEach(([v, w, q], i) => {
        if (q === 0) main.push({ v, w, id: i + 1 });
        else (attach[q] = attach[q] || []).push({ v, w });
    });

    // 初始化DP数组 价格为0-50
    const dp = new Array(n + 1).fill(0);

    // 处理每个主件及其可能的组合
    main.forEach((item) => {
        const { v, w } = item;
        const parts = attach[item.id] || [];

        // 生成所有可能的组合
        const combos = [
            { cost: v, value: v * w }, // 仅主件
            ...(parts[0]
                ? [
                      {
                          // 主件+附件1
                          cost: v + parts[0].v,
                          value: v * w + parts[0].v * parts[0].w,
                      },
                  ]
                : []),
            ...(parts[1]
                ? [
                      {
                          // 主件+附件2
                          cost: v + parts[1].v,
                          value: v * w + parts[1].v * parts[1].w,
                      },
                  ]
                : []),
            ...(parts[1]
                ? [
                      {
                          // 主件+两个附件
                          cost: v + parts[0].v + parts[1].v,
                          value:
                              v * w +
                              parts[0].v * parts[0].w +
                              parts[1].v * parts[1].w,
                      },
                  ]
                : []),
        ];

        // 更新DP数组
        // 重点：这里需要从大到小更新，因为每个主件只能选一次
        for (let j = n; j >= 0; j--) {
            for (const { cost, value } of combos) {
                if (j >= cost) {
                    const val = dp[j];
                    const val1 = dp[j - cost] + value;
                    dp[j] = Math.max(dp[j], dp[j - cost] + value);
                }
            }
        }
    });

    return dp[n];
}
void (async function () {
    // Write your code here
    const token = await readline();
    const totalPrice = parseInt(token.split(" ")[0]);
    const count = parseInt(token.split(" ")[1]);
    let inputs = [];
    let line = "";
    while ((line = await readline())) {
        inputs.push(line.split(" ").map((n) => parseInt(n)));
    }
    console.log(maxSatisfaction(totalPrice, count, inputs));
})();

发表于 2025-07-06 22:06:08 回复(0)

JavaScript Node

牛客555584396号

01背包问题，把数据分组分为a,b,c、a,b,[c+c(附件1)]、a,b,[c+c(附件2)]、a,b,[c+c(附件1)+c(附件2)]，分别计算各组的最大值，最后获取最大值列表中的最大值

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

let info = (await readline()).split(" ");

let budget = info[0];

let refIds = new Set();

let groups = [];

let data = [];

let id = 0;

// Write your code here

while ((line = await readline())) {

let tokens = line.split(" ");

id += 1;

let rId = parseInt(tokens[2])

data.push({

weight: parseInt(tokens[0]),

value: parseInt(tokens[1]) * parseInt(tokens[0]),

refId: rId,

id,

});

rId != 0 && refIds.add(rId);

}

// 获取主键列表

let mainItem = data.filter((v) => v.refId == 0);

let attachItem = data.filter((v) => v.refId != 0);

groups.push(mainItem);

refIds.forEach((rId) => {

groups.forEach((group) => {

let idAttachItem = attachItem.filter((v) => v.refId == rId);

idAttachItem.forEach((aItem) => {

let cpGroup = JSON.parse(JSON.stringify(group));

cpGroup = cpGroup.map((v) => {

if (aItem.refId === v.id) {

v.weight += aItem.weight;

v.value += aItem.value;

}

return v;

});

groups.push(cpGroup);

});

let cpGroup = JSON.parse(JSON.stringify(group));

idAttachItem.forEach((aItem) => {

cpGroup = cpGroup.map((v) => {

if (aItem.refId === v.id) {

v.weight += aItem.weight;

v.value += aItem.value;

}

return v;

});

groups.push(cpGroup);

});

let bag01 = function (weights, values, total) {

total = parseInt(total / 10);

let dp = new Array(total + 1).fill(0);

for (let i = 0; i < weights.length; i++) {

for (let j = total; j >= 0; j--) {

let curWeight = weights[i] / 10;

let curValue = values[i] / 10;

if (j - curWeight >= 0) {

dp[j] = Math.max(dp[j], dp[j - curWeight] + curValue);

}

return dp[total] * 10;

};

let maxValues = [];

groups.forEach((group, gi) => {

let weights = [],

values = [];

group.forEach((item, i) => {

weights.push(item.weight);

values.push(item.value);

});

let maxValue = bag01(weights, values, budget, gi);

maxValues.push(maxValue);

});

console.log(Math.max(...maxValues));

})();

发表于 2025-01-20 00:03:31 回复(0)

JavaScript Node

克先生

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    let inputs = []
    while(line = await readline()){
        inputs.push(line.split(' ').map(n=>parseInt(n)))
    }
    let n=0,m=0;
    let primary = {},annex = {}
    n = inputs[0][0]
    m = inputs[0][1]
    for(let i=1;i<m+1;i++){
        let x,y,z;
        [x,y,z] = inputs[i];
        if (z===0){
            // 主件
            primary[i]=[x,y]
        }else{
            // 附件
            if(annex[z]){
                // 已经有记录,添加附件,没有记录,新增附件列表
                annex[z].push([x,y])
            }else{
                annex[z] = [[x,y]]
            }
        }
    }

    m = Object.keys(primary).length; //数量转为主件数量
    dp = []
    for(let i=0;i<m+1;i++){
        let temp = []
        for(let j=0;j<n+1;j++){
            temp.push(0)
        }
        dp.push(temp)
    }

    let w = [[]], v= [[]]
    
    for(let key in primary){
        let w_temp=[], v_temp=[];
        w_temp.push(primary[key][0]); //主件价格
        v_temp.push(primary[key][0]*primary[key][1]) //满意度
        if (annex[key]){
            w_temp.push(w_temp[0]+annex[key][0][0])//主件+附件1
            v_temp.push(v_temp[0]+annex[key][0][0]*annex[key][0][1])
            if(annex[key].length===2){ 
            //2个附件
                w_temp.push(w_temp[0]+annex[key][1][0])//主件+附件2
                v_temp.push(v_temp[0]+annex[key][1][0]*annex[key][1][1])
                w_temp.push(w_temp[0]+annex[key][0][0]+annex[key][1][0])//主件+附件1+附件2
                v_temp.push(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
            }
        }
        w.push(w_temp);
        v.push(v_temp);
    }
    for (let i=1;i<m+1;i++){
        for(let j=10;j<n+1;j+=10){
            let max_i = dp[i-1][j]
            for(let k=0;k<w[i].length;k++){
                if(j-w[i][k]>=0){
                    max_i=Math.max(max_i,dp[i-1][j-w[i][k]]+v[i][k])
                }
            }
            dp[i][j]=max_i
        }
    }
    console.log(dp[m][n])
}()

https://blog.nowcoder.net/n/82b5f014a8654c8b8dbff4fe4fa727bd?f=comment 抄来的

发表于 2023-11-18 23:09:28 回复(0)

JavaScript Node

手谈丶

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

// Write your code here

let line1 = await readline();

let tokens = line1.split(" ");

let N = (parseInt(tokens[0]) / 10) | 0;

let m = parseInt(tokens[1]);

const items = [];

const map = new Map();

let id = 1;

while ((line = await readline())) {

let tokens = line.split(" ");

let v = parseInt(tokens[0]) / 10;

let p = parseInt(tokens[1]);

let q = parseInt(tokens[2]);

const item = { id, v, p, q, value: v * p };

if (item.q === 0) {

item.children = [];

}

items.push(item);

map.set(id, item);

id++;

}

for (let i = 0; i < items.length; i++) {

let item = items[i];

if (item.q !== 0) {

map.get(item.q).children.push(item);

}

const pItems = items.filter((item) => item.q === 0);

let dp = new Array(pItems.length + 1)

.fill()

.map(() => new Array(N + 1).fill(0));

const getDp = (i, j) => {

if (i < 0 || j < 0) {

return;

}

};

for (let i = 1; i <= pItems.length; i++) {

for (let j = 1; j <= N; j++) {

const item = pItems[i - 1];

const childNum = item.children.length;

if (j >= item.v) {

dp[i][j] = Math.max(

dp[i - 1][j],

dp[i - 1][j - item.v] + item.value

);

if (childNum === 1) {

let childItem = item.children[0];

if (j - item.v - childItem.v >= 0) {

dp[i][j] = Math.max(

dp[i][j],

dp[i - 1][j - item.v - childItem.v] +

item.value +

childItem.value

);

}

} else {

if (childNum === 2) {

let childItem1 = item.children[0];

let childItem2 = item.children[1];

if (j - item.v - childItem1.v >= 0) {

dp[i][j] = Math.max(

dp[i][j],

dp[i - 1][j - item.v - childItem1.v] +

item.value +

childItem1.value

);

}

if (j - item.v - childItem2.v >= 0) {

dp[i][j] = Math.max(

dp[i][j],

dp[i - 1][j - item.v - childItem2.v] +

item.value +

childItem2.value

);

}

if (j - item.v - childItem1.v-childItem2.v >= 0) {

dp[i][j] = Math.max(

dp[i][j],

dp[i - 1][

j - item.v - childItem1.v - childItem2.v

] +

item.value +

childItem1.value +

childItem2.value

);

}

} else {

dp[i][j] = dp[i - 1][j];

}

console.log(dp[pItems.length][N] * 10);

})();

发表于 2023-09-02 12:18:07 回复(0)

JavaScript Node

八冲寄紫

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    //1. 读取数据
    let token = [];
    while ((line = await readline())) {
        let tokens = line.split(" ");
        token.push(tokens.map(Number));
    }
    let [N, m] = token[0];
    let V = [0],
        W = [0],
        R = [0];
    let temp;
    for (let i = 1; i < token.length; i++) {
        V.push(token[i][0]);
        W.push(token[i][1]);
        R.push(token[i][2]);
    }

    //2. 分段
    //求最大公因数
    function gcd(a, b) {
        if (b == 0) {
            return a;
        }
        var r = a % b;
        return gcd(b, r);
    }
    //求一组数的最大公因数
    let gap = V.concat(N).reduce((prev, curr) => gcd(prev, curr));
    //统一单位大小
    V = V.map((v) => v / gap);
    //dp表
    let containerLength = N / gap;
    let container = new Array(containerLength + 1).fill(0);

    let inCart = new Array(containerLength + 1).fill(new Array(1).fill(0));
    for (let i = 1; i < m + 1; i++) {
        //前i个物体
        for (let j = containerLength; j >= V[i]; j--) {
            //容量为j
            let curr = j,
                before = j - V[i];
            let wealth,
                currValue,
                prevValue = container[curr];
            let [mainItemValue, mainItemWeight] = [V[R[i]], W[R[i]]];
            //       console.log(i,container);
            //       console.log(inCart[curr]);
            if (!inCart[before].includes(i)) {
                //没有重复当前的这个物件
                if (inCart[before].includes(R[i])) {
                    //如果主件已入购物车
                    wealth = V[i] * W[i];
                    currValue = container[j - V[i]] + wealth;
                    if (currValue > prevValue) {
                        container[j] = currValue;
                        inCart[curr] = inCart[before].concat([i]);
                    }
                } else if (j - mainItemValue - V[i] >= 0) {
                    //如果主件没进，那么考虑把主件也并在一起
                    wealth = mainItemValue * mainItemWeight + V[i] * W[i];
                    currValue = container[j - mainItemValue - V[i]] + wealth;
                    if (
                        !inCart[j - mainItemValue - V[i]].includes(i) &&
                        //                      !inCart[j-mainItemValue-V[i]].includes(R[i])  &&
                        currValue > prevValue
                    ) {
                        container[j] = currValue;
                        inCart[curr] = inCart[j - mainItemValue - V[i]].concat([
                            i,
                            R[i],
                        ]);
                    }
                }
            }
        }
    }
    console.log(container[containerLength] * gap);
})();

发表于 2023-06-17 16:48:46 回复(0)

JavaScript Node