请选择 进入手机版 | 继续访问电脑版

009背包问题求方案数

[复制链接]
卓小兔 发表于 2021-1-1 18:30:03 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题目形貌:

  有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi,代价是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不高出背包涵量,且总代价最大。
输出 最优选法的方案数。注意答案大概很大,请输出答案模 10^9+7 的效果。
输入格式:

  第一行两个整数,N,V用空格隔开,分别体现物品数量和背包涵积。
接下来有 N 行,每行两个整数 vi,wi用空格隔开,分别体现第 i件物品的体积和代价。
输出格式:

  输出一个整数,体现 方案数 模 10^9+7的效果。
数据范围:

<blockquote>  
0 N >> V;    for (int i = 1; i > v >> w;    for (int i = 0; i  right) g[j] = g[j];            else if (left < right) g[j] = g[j - v];            else g[j] = g[j] + g[j - v];            g[j] %= mod;        }    cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )