You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
// http://www.it61.cn/events/3758.html
/**
背包 换金币
-----------------------------------------------------------
可承受重量M 手中的金额M
N类物品 N种纪念币
每类物品的重量Wi 买入时多少钱, 占用了M的份额
每类物品的价值Vi 卖出时多少钱-买入时多少钱,表示获利
每类物品的数量是无穷的
问:这个背包可以装载物品的最大价值是多少?
*/
int T , N , M ;
int f [ 10001 ] ; //dp表
int p [ 101 ] [ 10001 ] ; //第一维表示是第几天,第二维表示是哪个纪念品,值表示是当天这个纪念品多少钱
int main ( ) {
//输入+输出重定向
freopen ( " ../1298.txt " , " r " , stdin ) ;
cin > > T > > N > > M ; //T:天数, N:纪念品种类 M:小伟现在拥有的金币数量
//循环读入每一天,每一种纪念品的价格到数组中
for ( int i = 1 ; i < = T ; + + i ) {
for ( int j = 1 ; j < = N ; + + j ) {
cin > > p [ i ] [ j ] ;
}
}
for ( int i = 2 ; i < = T ; i + + ) { //从第2天起到第T天止,因为第一天就算是买了再卖了,也是赚不到钱的
//每一天都需要清空dp表一次
memset ( f , 0 , sizeof ( f ) ) ;
//下面是一个标准的完全背包,就是物品没有个数限制,但背包容量上限是固定的。
//占用资源数= price[i-1][j]
//获得的利益= 今天的价格 - 前一天的价格=price[i][j] - price[i - 1][j]
for ( int j = 1 ; j < = N ; j + + ) { //遍历每一种纪念品
for ( int k = p [ i - 1 ] [ j ] ; k < = M ; k + + ) { //构建DP表, 完全是按照完全背包的模板来写的代码,参照1297.cpp
f [ k ] = max ( f [ k ] , f [ k - p [ i - 1 ] [ j ] ] + p [ i ] [ j ] - p [ i - 1 ] [ j ] ) ;
}
}
//最大利润合计(dp[M]里面保存的,其实就是当天的最大收益)
//cout << "dp[M]=" << dp[M] << ",M=" << M << endl;
M + = f [ M ] ;
}
cout < < M < < endl ;
//关闭文件
fclose ( stdin ) ;
return 0 ;
}