背包问题算法设计.docx
版权申诉
40 浏览量
2022-05-08
13:12:07
上传
评论
收藏 13KB DOCX 举报
背包问题算法设计
题目描述：
有n个物品，每个 物 品 的 重 量 为 w[i]， 取 物 品 则 效 益 增 加 p[i]，对于给
定的一个能容 纳 重 量 为 M的背包，怎样装 包 才 能 使 获 得 的 效 益 最 大 ？ 每 个
物品的取值为 x[i]，x[i]=0/1，0表示 该 物 品 不 装 包 ， 1表 示 将 该 物 品 装 入 包
中。
以上描述就是 一 个 经 典 的 0/1背包问题 。
输入输出：
输入一个 n， 然 后 输 入 w[1,2,...,n],p[1,2,...,n]
输出最大效益 值 和 x[1,2,...,n]用 0/1表 示
sampleinput
3//n
234//w[i]
125//p[i]
sampleoutput
6//最 大 效 益 值
101//x[i]
解题思路：
资源评论
