01背包问题:DP
2024-09-11 20:05:09
题目描述:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
二维做法:
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int v[1010], w[1010], f[1010][1010];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)//j要从0开始,
{
f[i][j] = f[i - 1][j];//物品重量大于背包重量,没法取
if (j >= v[i])
{
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);// max(不取,取)
}
}
cout << f[n][m] << "\n";// f[n][m]即为最大值
return 0;
}
一维做法:
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int v[1010], w[1010], f[1010];// f[j]:容量为j所能取得的最大值
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);// max(不取,取)
}
cout << f[m] << "\n";//f[m]即最大值
return 0;
}
最新文章
- Autocad 2012 win7(64位)启动时一直卡在acmgd.dll处的解决方案
- MVC html.actionlink
- 十分钟入门less(翻译自:Learn lESS in 10 Minutes(or less))
- eclipse文本编码格式修改为UTF-8 (转)
- MySql数据库安装&;修改密码&;开启远程连接图解
- python select
- easyui tree 折叠节点
- Run UliPad 4.1 Under Windows 7 64bit and wxPython 3.0.2
- BUFFER CACHE之调整buffer cache的大小
- php 加密解密方法
- ARPU值分析
- JMessage是让App 同时集成 Push 功能与 IM 功能最完美的方案
- 面试之路(28)-反转链表(reverse ListNode)
- ScalaPB(5):用akka-stream实现reactive-gRPC
- 在js文件中通过jquery定位到某个dom时候设置事件时候 相当于直接在dom里面添加事件
- css干货部分
- webstorm安装教程
- 201621123001 《java程序设计》第2周学习总结
- 如何解决VMware 12 安装Ubuntu 16.04时无网络连接问题
- 2013级计算机学院数字媒体专业李成梁(笛卡尔积,概率树状图)&; 学生选课
热门文章
- mysql where 加 多个 或者条件
- iOS之创建通知、发送通知和移除通知的坑
- 自动曝光修复算法 附完整C代码
- Cannot send session cache limiter - headers already sent问题
- Learning Experience of Big Data: Deploying Tomcat 8.0 and connect ssh without password
- python学习——面向对象的三大特性
- 树莓派安装samba
- xshell5连接虚拟机的小问题处理
- OI生涯回忆录(一)
- 北京Uber优步司机奖励政策(2月26日)