【題目鏈接】
ybt 1844：【06NOIP提高組】金明的預算方案
洛谷 P1064 [NOIP2006 提高組] 金明的預算方案
【題目考點】
1. 動態(tài)規(guī)劃：分組背包
2. 動態(tài)規(guī)劃：依賴背包
【解題思路】
解法1：分組背包
已知第i個商品的價格v[i]，重要程度w[i]，求出第i個商品的價值c[i] = v[i]*w[i]
狀態(tài)定義：dp[i][j]為使用j元錢買前i個主件及其附件能得到的最大價值狀態(tài)轉(zhuǎn)移方程：思考已有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：依賴背包
該問題的配件數(shù)最多2個，配件的組合情況比較容易得到。如果有x個配件，那配件的組合情況將為x個元素構(gòu)成的集合的子集個數(shù)，為2x2^x2x個。當x較大時，就無法計算了。
依賴背包的思路為：針對每個主件該如何選附件，做一次小的01背包問題，求在不同金錢限制下，在對附件做不同選擇時得到最大價值。
已知第i個商品的價格v[i]，重要程度w[i]，求出第i個商品的價值c[i] = v[i]*w[i]
狀態(tài)定義：dp[i][j]為使用j元錢買前i個主件及其附件能得到的最大價值狀態(tài)轉(zhuǎn)移：
外層循環(huán)i從1到m，每次循環(huán)求出在擁有任意錢數(shù)（錢數(shù)范圍0~n）下，買前i個主件及其附件能得到的最大價值
(1) 不買第i主件，那么無論j為任意值，dp[i][j] = dp[i-1][j]
(2)j為任意值，確定要買第i主件，那么一定有j >= v[i]，
設(shè)狀態(tài)dp1[k][j]表示j元錢買前i-1個主附件、第i個主件以及第i主件的前k個配件可以得到的最大價值。
(3)dp1的初始狀態(tài)：dp1[0][j]為只買第i主件不買配件的情況，即為用j-v[i]的錢買前i-1個主件得到的最大價值加上第i主件的價值c[i]。即dp1[0][j] = dp[i][j-v[i]]+c[i]
(4)此時針對dp1狀態(tài)做01背包問題，外層循環(huán)遍歷i的各個附件，內(nèi)層為可以使用的錢數(shù)，主要這個錢數(shù)包括了主件的花銷。
記第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的附件個數(shù)。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
;Item(){}Item(int a
, int b
):v(a
),c(b
){}
};
Item a
[M
];
vector
<Item
> g
[M
];
vector
<int> f
[M
];
int dp
[M
][N
];
int main()
{int n
, m
, v
, p
, q
, zn
;cin
>> n
>> m
;for(int i
= 1; i
<= m
; ++i
){cin
>> v
>> p
>> q
;a
[i
].v
= v
;a
[i
].c
= v
*p
;if(q
== 0)g
[i
].push_back(a
[i
]);elsef
[q
].push_back(i
);}for(int i
= 1; i
<= m
; ++i
){if(g
[i
].size() > 0){ int i1
, i2
;if(f
[i
].size() == 1){i1
= f
[i
][0];g
[i
].push_back(Item(a
[i
].v
+a
[i1
].v
, a
[i
].c
+a
[i1
].c
));}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
));g
[i
].push_back(Item(a
[i
].v
+a
[i2
].v
, a
[i
].c
+a
[i2
].c
));g
[i
].push_back(Item(a
[i
].v
+a
[i1
].v
+a
[i2
].v
, a
[i
].c
+a
[i1
].c
+a
[i2
].c
));}}}for(int i
= 1; i
<= m
; ++i
){for(int j
= 0; j
<= n
; ++j
){dp
[i
][j
] = dp
[i
-1][j
];for(int k
= 0; k
< g
[i
].size(); ++k
){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;
}
- 滾動數(shù)組優(yōu)化，變?yōu)橐痪S狀態(tài)
#include<bits/stdc++.h>
using namespace std
;
#define M 65
#define N 40000
struct Item
{int v
, c
;Item(){}Item(int a
, int b
):v(a
),c(b
){}
};
Item a
[M
];
vector
<Item
> g
[M
];
vector
<int> f
[M
];
int dp
[N
];
int main()
{int n
, m
, v
, p
, q
, zn
;cin
>> n
>> m
;for(int i
= 1; i
<= m
; ++i
){cin
>> v
>> p
>> q
;a
[i
].v
= v
;a
[i
].c
= v
*p
;if(q
== 0)g
[i
].push_back(a
[i
]);elsef
[q
].push_back(i
);}for(int i
= 1; i
<= m
; ++i
){if(g
[i
].size() > 0){ int i1
, i2
;if(f
[i
].size() == 1){i1
= f
[i
][0];g
[i
].push_back(Item(a
[i
].v
+a
[i1
].v
, a
[i
].c
+a
[i1
].c
));}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
));g
[i
].push_back(Item(a
[i
].v
+a
[i2
].v
, a
[i
].c
+a
[i2
].c
));g
[i
].push_back(Item(a
[i
].v
+a
[i1
].v
+a
[i2
].v
, a
[i
].c
+a
[i1
].c
+a
[i2
].c
));}}}for(int i
= 1; i
<= m
; ++i
){if(g
[i
].size() == 0)continue;for(int j
= n
; j
>= 0; --j
){for(int k
= 0; k
< g
[i
].size(); ++k
){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
;Item(){}Item(int a
, int b
):v(a
),c(b
){}
};
Item a
[M
];
vector
<int> f
[M
];
int dp
[M
][N
];
int dp1
[5][N
];
bool isMain
[M
];
int main()
{int n
, m
, v
, p
, q
;cin
>> n
>> m
;for(int i
= 1; i
<= m
; ++i
){cin
>> v
>> p
>> q
;a
[i
].v
= v
;a
[i
].c
= v
*p
;if(q
> 0)f
[q
].push_back(i
);elseisMain
[i
] = true;}for(int i
= 1; i
<= m
; ++i
){int pnum
= f
[i
].size();for(int j
= 0; j
<= n
; ++j
)dp
[i
][j
] = dp
[i
-1][j
];if(isMain
[i
] == false)continue; memset(dp1
, 0, sizeof(dp1
));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
){ int vx
= a
[f
[i
][k
-1]].v
, cx
= a
[f
[i
][k
-1]].c
;for(int j
= a
[i
].v
; j
<= n
; ++j
){if(j
-a
[i
].v
>= vx
)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;
}
- 滾動數(shù)組優(yōu)化 一維狀態(tài)
#include<bits/stdc++.h>
using namespace std
;
#define M 65
#define N 40000
struct Item
{int v
, c
;Item(){}Item(int a
, int b
):v(a
),c(b
){}
};
Item a
[M
];
vector
<int> f
[M
];
int dp
[N
];
int dp1
[N
];
bool isMain
[M
];
int main()
{int n
, m
, v
, p
, q
;cin
>> n
>> m
;for(int i
= 1; i
<= m
; ++i
){cin
>> v
>> p
>> q
;a
[i
].v
= v
;a
[i
].c
= v
*p
;if(q
> 0)f
[q
].push_back(i
);elseisMain
[i
] = true;}for(int i
= 1; i
<= m
; ++i
){int pnum
= f
[i
].size();if(isMain
[i
] == false)continue; memset(dp1
, 0, sizeof(dp1
));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
){ int vx
= a
[f
[i
][k
-1]].v
, cx
= a
[f
[i
][k
-1]].c
;for(int j
= n
; j
>= a
[i
].v
+vx
; --j
)dp1
[j
] = max(dp1
[j
], dp1
[j
-vx
]+cx
);}for(int j
= a
[i
].v
; j
<= n
; ++j
)dp
[j
] = max(dp
[j
], dp1
[j
]);}cout
<< dp
[n
];return 0;
}
新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！
總結(jié)
以上是生活随笔為你收集整理的信息学奥赛一本通 1844：【06NOIP提高组】金明的预算方案 | 洛谷 P1064 [NOIP2006 提高组] 金明的预算方案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
