信息学奥赛一本通 1844：【06NOIP提高组】金明的预算方案 | 洛谷 P1064 [NOIP2006 提高组] 金明的预算方案

【题目链接】

ybt 1844：【06NOIP提高组】金明的预算方案
洛谷 P1064 [NOIP2006 提高组] 金明的预算方案

【题目考点】

1. 动态规划：分组背包

2. 动态规划：依赖背包

【解题思路】

解法1：分组背包

已知第i个商品的价格v[i]，重要程度w[i]，求出第i个商品的价值c[i] = v[i]*w[i]

状态定义：dp[i][j]为使用j元钱买前i个主件及其附件能得到的最大价值

状态转移方程：思考已有j元钱，如何购买第i个主件及其附件

如果不买第i个主件及其附件，dp[i][j]为使用j元钱买前i-1个主件及其附件能得到的最大价值，即dp[i][j] = dp[i-1][j]

如果买第i个主件及其附件，这里要把第i个主件及其选择的附件整合成一个商品。该商品的价格是选择的主、附件商品的价格的和，价值是选择的主、附件商品价值的和。这些整合的商品相当于一个商品组，在这一组中只能选择其中一种商品。这就是分组背包的模型。

1)如果只选主件，那么该商品价格为v[i]，价值为c[i]。
2)如果该主件存在1个附件i1，选择主件及第1个附件，整合后的商品价格为 v[i]+v[i1]，价值为c[i]+c[i1]。
3)如果该主件存在2个附件i1与i2，选择主件与第2个附件，整合后商品的价格为v[i]+v[i2]，价值为c[i]+c[i2]。
4)如果该主件存在2个附件i1与i2，选择主件与第1，2个附件，整合后商品的价格为v[i]+v[i1]+v[i2]，价值为c[i]+c[i1]+c[i2]。

记整合后的商品价格为vx，价值为cx，那么如果买这个整合后的商品
dp[i][j]为使用j-vx元钱买前i-1个主件及其附件能得到的最大价值加上cx，即dp[i][j] = dp[i-1][j-vx]+cx。
把买每种可能的整合商品时的dp[i][j]都求出来。

将在第1点和第2点中求出的所有dp[i][j]求最大值，作为dp[i][j]的值。

解法2：依赖背包

该问题的配件数最多2个，配件的组合情况比较容易得到。如果有x个配件，那配件的组合情况将为x个元素构成的集合的子集个数，为$2^x$个。当x较大时，就无法计算了。
依赖背包的思路为：针对每个主件该如何选附件，做一次小的01背包问题，求在不同金钱限制下，在对附件做不同选择时得到最大价值。
已知第i个商品的价格v[i]，重要程度w[i]，求出第i个商品的价值c[i] = v[i]*w[i]

状态定义：dp[i][j]为使用j元钱买前i个主件及其附件能得到的最大价值

状态转移：
外层循环i从1到m，每次循环求出在拥有任意钱数（钱数范围0~n）下，买前i个主件及其附件能得到的最大价值
(1) 不买第i主件，那么无论j为任意值，dp[i][j] = dp[i-1][j]
(2)j为任意值，确定要买第i主件，那么一定有j >= v[i]，
设状态dp1[k][j]表示j元钱买前i-1个主附件、第i个主件以及第i主件的前k个配件可以得到的最大价值。
(3)dp1的初始状态：dp1[0][j]为只买第i主件不买配件的情况，即为用j-v[i]的钱买前i-1个主件得到的最大价值加上第i主件的价值c[i]。即dp1[0][j] = dp[i][j-v[i]]+c[i]
(4)此时针对dp1状态做01背包问题，外层循环遍历i的各个附件，内层为可以使用的钱数，主要这个钱数包括了主件的花销。
记第k附件价格为vx，价值为cx。
如果剩余的钱买了该附件后，剩下的钱还足够买主件，即j-vx >= v[i]，那么买该附件的价值为用j-vx的钱买前k-1个附件（包括第i主件与前i-1个主件的东西）的最大价值加上第k附件的价值。不买该附件，那就是用j的钱买前k-1个附件（包括第i主件与前i-1个主件的东西）能得到的最大价值。二者取最大值。为：dp1[k][j] = max(dp1[k-1][j], dp1[k-1][j-vx]+cx);
如果买了该附件后，剩下的钱无法再买主件，那么不买该附件。
(5)pnum为主件i的附件个数。dp1[pnum][j]即为用j元钱购买前i-1个主附件、第i主件以及i的前pnum个附件能获得的最大价值。而dp[i][j]的概念为用j元钱购买前i个物品的主附件能获得的最大价值，二者的概念是等同的。所以这里用dp1[pnum][j]的值更新dp[i][j]的值，取最大值。

【题解代码】

解法1：分组背包

• 二维状态

#include<bits/stdc++.h> using namespace std; #define M 65 #define N 40000 struct Item {int v, c;//v:价格 c:价值：为价格*重要程度Item(){}Item(int a, int b):v(a),c(b){} }; Item a[M];//a[i]:第i个物品 vector<Item> g[M];//g[i]为第i个商品分组，即保存主件i的所有可能整合商品（包括有无附件）， vector<int> f[M];//f[i]中保存主件i的附件的编号， int dp[M][N];//dp[i][j]:使用j元钱买前i个主件及其可能的附件能得到的最大价值 int main() {int n, m, v, p, q, zn;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> v >> p >> q;//v价格，p重要程度，q对应主件 a[i].v = v;//第i商品价格 a[i].c = v*p;//第i商品价值 if(q == 0)//如果q是主件g[i].push_back(a[i]);//分组i添加商品 else//如果q是附件 f[q].push_back(i);//主件q的配件列表增加i }for(int i = 1; i <= m; ++i)//构造商品分组{if(g[i].size() > 0)//如果分组i中有商品，说明i是主件{ int i1, i2;//现在要看主件i商品 i1,i2:附件 if(f[i].size() == 1)//如果只有1个附件 {i1 = f[i][0];g[i].push_back(Item(a[i].v+a[i1].v, a[i].c+a[i1].c));//整合主件与附件1 }else if(f[i].size() == 2){i1 = f[i][0], i2 = f[i][1];g[i].push_back(Item(a[i].v+a[i1].v, a[i].c+a[i1].c));//主件与附件1 g[i].push_back(Item(a[i].v+a[i2].v, a[i].c+a[i2].c));//主件与附件2 g[i].push_back(Item(a[i].v+a[i1].v+a[i2].v, a[i].c+a[i1].c+a[i2].c));//主件与附件1，2 }}}for(int i = 1; i <= m; ++i)//选择主件m {for(int j = 0; j <= n; ++j)//最大钱数{dp[i][j] = dp[i-1][j];//不买主件i及其附件。如果遇到附件，也要运行这一句。 for(int k = 0; k < g[i].size(); ++k)//选择分组i中的一个商品。如果是附件，g[i].size()为0，该循环不会运行 {int vx = g[i][k].v, cx = g[i][k].c;if(j >= vx) dp[i][j] = max(dp[i][j], dp[i-1][j-vx]+cx);} }}cout << dp[m][n];return 0; }

• 滚动数组优化，变为一维状态

#include<bits/stdc++.h> using namespace std; #define M 65 #define N 40000 struct Item {int v, c;//v:价格 c:价值：为价格*重要程度Item(){}Item(int a, int b):v(a),c(b){} }; Item a[M];//a[i]:第i个物品 vector<Item> g[M];//g[i]为第i个商品分组，即保存主件i的所有可能整合商品（包括有无附件）， vector<int> f[M];//f[i]中保存主件i的附件的编号， int dp[N];//滚动数组优化为1维数组 原状态：dp[i][j]:使用j元钱买前i个主件及其可能的附件能得到的最大价值 int main() {int n, m, v, p, q, zn;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> v >> p >> q;//v价格，p重要程度，q对应主件 a[i].v = v;//第i商品价格 a[i].c = v*p;//第i商品价值 if(q == 0)//如果q是主件g[i].push_back(a[i]);//分组i添加商品 else//如果q是附件 f[q].push_back(i);//主件q的配件列表增加i }for(int i = 1; i <= m; ++i){if(g[i].size() > 0)//如果分组i中有商品，说明i是主件{ int i1, i2;//现在要看主件i商品 i1,i2:附件 if(f[i].size() == 1)//如果只有1个附件 {i1 = f[i][0];g[i].push_back(Item(a[i].v+a[i1].v, a[i].c+a[i1].c));//整合主件与附件1 }else if(f[i].size() == 2){i1 = f[i][0], i2 = f[i][1];g[i].push_back(Item(a[i].v+a[i1].v, a[i].c+a[i1].c));//主件与附件1 g[i].push_back(Item(a[i].v+a[i2].v, a[i].c+a[i2].c));//主件与附件2 g[i].push_back(Item(a[i].v+a[i1].v+a[i2].v, a[i].c+a[i1].c+a[i2].c));//主件与附件1，2 }}}for(int i = 1; i <= m; ++i)//选择主件m {if(g[i].size() == 0)continue;for(int j = n; j >= 0; --j)//最大钱数{for(int k = 0; k < g[i].size(); ++k)//选择分组i中的一个商品。如果是附件，g[i].size()为0，该循环不会运行 {int vx = g[i][k].v, cx = g[i][k].c;if(j >= vx) dp[j] = max(dp[j], dp[j-vx]+cx);} }}cout << dp[n];return 0; }

解法2：依赖背包

• 二维状态

#include<bits/stdc++.h> using namespace std; #define M 65 #define N 40000 struct Item {int v, c;//v:价格 c:价值：为价格*重要程度Item(){}Item(int a, int b):v(a),c(b){} }; Item a[M];//a[i]:第i个物品 vector<int> f[M];//f[i]中保存主件i的附件的编号， int dp[M][N];//dp[i][j]:使用j元钱买前i个主件及其可能的附件能得到的最大价值 int dp1[5][N];//dp1[i][j]:在关注某主件i的情况下，j元钱购买i的前k个附件可以得到的最大价值 bool isMain[M];//isMain[i]:i是不是主件 int main() {int n, m, v, p, q;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> v >> p >> q;//v价格，p重要程度，q对应主件 a[i].v = v;//第i商品价格 a[i].c = v*p;//第i商品价值 if(q > 0)f[q].push_back(i);//主件q的配件列表增加i elseisMain[i] = true;}for(int i = 1; i <= m; ++i)//选择主件m {int pnum = f[i].size();//配件数量 for(int j = 0; j <= n; ++j)//最大钱数dp[i][j] = dp[i-1][j];//不买主件i及其附件。如果遇到附件，也要运行这一句。if(isMain[i] == false)//i是附件continue; memset(dp1, 0, sizeof(dp1));//dp1[k][j]:j元钱购买1~i-1的主副件及第i主件及i的前k个附件可以得到的最大价值for(int j = a[i].v; j <= n; ++j)//初始情况：不添加附件 只添加主件 dp1[0][j] = dp[i-1][j-a[i].v] + a[i].c;for(int k = 1; k <= pnum; ++k)//选择i的第k个附件{ int vx = a[f[i][k-1]].v, cx = a[f[i][k-1]].c;//配件k的价格和价值。vector下标从0开始，所以用的时候写k-1。 for(int j = a[i].v; j <= n; ++j){if(j-a[i].v >= vx)//买主件后剩下的钱还可以买第k附件 dp1[k][j] = max(dp1[k-1][j], dp1[k-1][j-vx]+cx);elsedp1[k][j] = dp1[k-1][j];}}for(int j = a[i].v; j <= n; ++j)dp[i][j] = max(dp[i][j], dp1[pnum][j]);}cout << dp[m][n];return 0; }

• 滚动数组优化 一维状态

#include<bits/stdc++.h> using namespace std; #define M 65 #define N 40000 struct Item {int v, c;//v:价格 c:价值：为价格*重要程度Item(){}Item(int a, int b):v(a),c(b){} }; Item a[M];//a[i]:第i个物品 vector<int> f[M];//f[i]中保存主件i的附件的编号， int dp[N];//滚动数组优化 dp[i][j]:使用j元钱买前i个主件及其可能的附件能得到的最大价值 int dp1[N];//滚动数组优化 dp1[i][j]:在关注某主件i的情况下，j元钱购买i的前k个附件可以得到的最大价值 bool isMain[M];//isMain[i]:i是不是主件 int main() {int n, m, v, p, q;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> v >> p >> q;//v价格，p重要程度，q对应主件 a[i].v = v;//第i商品价格 a[i].c = v*p;//第i商品价值 if(q > 0)f[q].push_back(i);//主件q的配件列表增加i elseisMain[i] = true;}for(int i = 1; i <= m; ++i)//选择主件m {int pnum = f[i].size();//配件数量 if(isMain[i] == false)//i是附件continue; memset(dp1, 0, sizeof(dp1));//dp1[k][j]:j元钱购买1~i-1的主副件及第i主件及i的前k个附件可以得到的最大价值for(int j = a[i].v; j <= n; ++j)//初始情况：不添加附件 只添加主件 dp1[j] = dp[j-a[i].v] + a[i].c;for(int k = 1; k <= pnum; ++k)//选择i的第k个附件{ int vx = a[f[i][k-1]].v, cx = a[f[i][k-1]].c;//配件k的价格和价值。vector下标从0开始，所以用的时候写k-1。 for(int j = n; j >= a[i].v+vx; --j)dp1[j] = max(dp1[j], dp1[j-vx]+cx);//买主件后剩下的钱还可以买第k附件 }for(int j = a[i].v; j <= n; ++j)dp[j] = max(dp[j], dp1[j]);}cout << dp[n];return 0; } 新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的信息学奥赛一本通 1844：【06NOIP提高组】金明的预算方案 | 洛谷 P1064 [NOIP2006 提高组] 金明的预算方案的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。