怀化组织部网站,微信网站html5,wordpress导航页面模板下载地址,2345查询网【题目链接】
ybt 1984#xff1a;【19CSPJ普及组】纪念品 洛谷 P5662 [CSP-J2019] 纪念品
【题目考点】
1. 动态规划#xff1a;完全背包
【解题思路】
由于小伟每天都可以买卖物品无限次#xff0c;我们可以假想每天开始时#xff0c;他把所有的商品都卖出#xff…【题目链接】
ybt 1984【19CSPJ普及组】纪念品 洛谷 P5662 [CSP-J2019] 纪念品
【题目考点】
1. 动态规划完全背包
【解题思路】
由于小伟每天都可以买卖物品无限次我们可以假想每天开始时他把所有的商品都卖出看用手中的钱该买哪些商品。 到第二天又可以卖出商品换钱了因此只需要考虑商品在当天及第二天的差价差价越高今天买该商品到第二天升值越多。 结合购买纪念品的背景每件商品可以购买无限件因此在第i天买入商品到第i1天卖出所有商品想要赚到最多的钱币该问题实际是一个完全背包问题。
背包容量小伟第i天拥有的钱币数物品重量每件物品在第i天的价格物品价值每件物品第i1天的价格减去第i天的价格差价能装入背包中的所有物品的最大价值从第i天到第i1天小伟赚到的钱币数也就是第i1天比第i天多获得钱币的最大值。 t为总天数循环变量i从1循环到t-1每次循环使用完全背包方法求在第i天买入商品到第i1天卖出所有商品后多赚到的钱币在原钱币数量基础上增加赚到钱币的数量该钱币数量作为下一天购买商品可以使用的总钱数也就是背包容量。 最后输出总钱数。
【题解代码】
解法1完全背包 二维状态
#include bits/stdc.h
using namespace std;
#define N 105
#define M 10005
int p[N][N];//p[i][j]第i天第j纪念品的价格
int w[N], c[N], dp[N][M];//dp[i][j]前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{int t, n, m;cin t n m;for(int i 1; i t; i)for(int j 1; j n; j)cin p[i][j];for(int i 1; i t; i){for(int j 1; j n; j){w[j] p[i][j]; c[j] p[i1][j]-p[i][j];}for(int k 1; k n; k)for(int j 1; j m; j){if(j w[k])dp[k][j] max(dp[k-1][j], dp[k][j-w[k]]c[k]);elsedp[k][j] dp[k-1][j];}m dp[n][m];//总钱数增加相邻两天多赚到的最大钱币数 }cout m; return 0;
}解法2完全背包 滚动数组优化
#include bits/stdc.h
using namespace std;
#define N 105
#define M 10005
int p[N][N];//p[i][j]第i天第j纪念品的价格
int w[N], c[N], dp[M];//dp[i][j]前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{int t, n, m;cin t n m;for(int i 1; i t; i)for(int j 1; j n; j)cin p[i][j];for(int i 1; i t; i){for(int j 1; j n; j){w[j] p[i][j]; c[j] p[i1][j]-p[i][j];}memset(dp, 0, sizeof(dp));for(int k 1; k n; k)for(int j w[k]; j m; j)dp[j] max(dp[j], dp[j-w[k]]c[k]);m dp[m];//总钱数增加相邻两天多赚到的最大钱币数 }cout m; return 0;
}
