HDU2639
有深度吧感覺(jué)還
題意：給出一行價(jià)值，一行體積，讓你在v體積的范圍內(nèi)找出第k大的值
終結(jié)第k大的01背包，
復(fù)雜度： O(NMK)
注意選取的標(biāo)準(zhǔn)，選取后，要保證得到的價(jià)值是大于未選之前，選之后若是相等的話，這樣應(yīng)該是不能選的，因?yàn)檎加昧丝臻g
?

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; const ll moad=1e9+7; const int maxn=1e6+10; int dp[1005][35]; int w[1005]; int c[1005]; int A[1005]; int B[1005]; int main() {int t;int n,m,K;cin>>t;while(t--){cin>>n>>m>>K;for(int i=0;i<n;++i)cin>>w[i];for(int i=0;i<n;++i)cin>>c[i];memset(dp,0,sizeof(dp));memset(A,0,sizeof(A)),memset(B,0,sizeof(B));for(int i=0;i<n;++i){for(int j=m;j>=c[i];--j){for(int k=1;k<=K;++k){A[k]=dp[j-c[i]][k]+w[i];//yesB[k]=dp[j][k];//no}int a=1,b=1,c=1;while(c<=K&&(a<=K||b<=K)){if(A[a]>B[b]) dp[j][c]=A[a],++a;else dp[j][c]=B[b],++b;if(dp[j][c]!=dp[j][c-1])++c;}}}cout<<dp[m][K]<<endl;}return 0; }

HDU2126
題意：給出n個(gè)不同得數(shù)字，然后給出一個(gè)m,問(wèn)使得挑選的數(shù)字的個(gè)數(shù)盡量多（這些數(shù)字之和小于等于m)，輸出最多挑選的數(shù)字個(gè)數(shù)是多少個(gè)，
并求出用這個(gè)最多的數(shù)字，作為挑選得數(shù)字的個(gè)數(shù),然后這些個(gè)數(shù)字之和<=m，成立的方案數(shù)有多少種,
貪心+二維費(fèi)用01背包，開(kāi)始只想到貪心的如何購(gòu)買(mǎi)到最多多少件，要求出購(gòu)買(mǎi)的方案數(shù)，~~母雞，
轉(zhuǎn)載：
有n件物品，每件物品都有自己得價(jià)格，旅客一共有m塊大洋。
第一個(gè)問(wèn)題，旅客最多可以買(mǎi)多少件物品？請(qǐng)注意，這里是多少件，不是價(jià)值最大。所以這個(gè)非常好求，將所有的物品按照價(jià)值排序，先買(mǎi)便宜的，再買(mǎi)貴的。
貪心的思想。要注意一些邊界問(wèn)題
用這種方法，我們可以求出旅客最多買(mǎi)多少件物品，求出之后，物品的價(jià)格就有了兩種屬性，一種是錢(qián)數(shù)，一種是件數(shù)。也就是買(mǎi)一件物品需要的消耗是它的價(jià)格的錢(qián)數(shù)和1件物品的份額。在背包九講中，這個(gè)叫做二維費(fèi)用的背包問(wèn)題。
如果是求最優(yōu)方案(這些個(gè)金錢(qián)m和最多的件數(shù)可以得到的最大價(jià)值)，這個(gè)問(wèn)題依舊毫無(wú)壓力。

但是現(xiàn)在的問(wèn)題是求方案總數(shù)。
所以就可以轉(zhuǎn)化為二位費(fèi)用得背包問(wèn)題 ?(重點(diǎn)，再看了整數(shù)拆分之后回過(guò)頭來(lái)看這個(gè)問(wèn)題，他是用的二位費(fèi)用的01背包來(lái)求解最大的！！！方案數(shù)！！是方案數(shù)注意轉(zhuǎn)移方程的含義，
就等于把一個(gè)數(shù)n劃分為由若干個(gè)不同的整數(shù)之和得到的，那么就是每個(gè)數(shù)字只能選或者不選,而且那道題是1維費(fèi)用(數(shù)字的大小,整數(shù)拆分三的第五問(wèn))把n當(dāng)作為背包容量,1~n當(dāng)作物品件數(shù)
先思考表達(dá)式的含義應(yīng)該是數(shù)字i由前j個(gè)(1~j)不同的數(shù)組成得到的最大方案數(shù) 得dp[i][j]=dq

我們用dp[j][k]表示花費(fèi)j元買(mǎi)k件物品的方案數(shù)，實(shí)際上很容易我們就可以得到dp[j][k]=dp[j][k]+dp[j-a[i]][k-1]。
關(guān)于這個(gè)方程有兩個(gè)需要特別解釋的地方，第一個(gè)這個(gè)是空間優(yōu)化(dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-a[i]][k-1])后的方程，優(yōu)化后的原理參見(jiàn)背包九講第一講01背
在考慮第i-1件物品后dp[j][k]的方案數(shù)。這個(gè)解釋了這個(gè)dp[j][k]為什么可以直接繼承過(guò)來(lái)。第二個(gè)需要解釋的是，在dp[j][k]和dp[j-a[i]][k-1]中有沒(méi)有相同的方案，即我們有沒(méi)有冒著重復(fù)計(jì)算的風(fēng)險(xiǎn)將兩者相加。答案是沒(méi)有。
因?yàn)樵赿p[j-a[i]][k-1]這些方案中都有第i件物品，我們說(shuō)過(guò)dp[j][k]實(shí)際上是dp[i-1][j][k]，其中根本沒(méi)有第i件物品的影子，所以兩者不可能有重復(fù)的方案。

實(shí)際上如果了解第k大背包的算法的話，會(huì)對(duì)解決這道題有很大幫助。

幾天了再回過(guò)頭來(lái)看看這道題感覺(jué)算是個(gè)二位費(fèi)用得01背包水題吧,把商品得價(jià)值和價(jià)值和件數(shù)都作為背包的屬性，總的價(jià)值和貪心得得到得最多可以購(gòu)買(mǎi)的數(shù)量作為背包得容量。
不過(guò)初始化問(wèn)題還是要考慮注意一下為啥要這樣得
?

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=1e6+10; int dp[1005][1005]; int w[1005]; int main() {int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=0;i<n;++i)cin>>w[i];sort(w,w+n);int cnt=0,ans=0;for(int i=0;i<n;++i){ans+=w[i],cnt++;if(ans>m)break;}if(ans>m) --cnt;if(!cnt){cout<<"Sorry, you can't buy anything."<<endl;continue;}memset(dp,0,sizeof(dp));for(int i=0;i<=m;++i)dp[i][0]=1;for(int i=0;i<n;++i){for(int j=m;j>=w[i];--j){for(int k=cnt;k>=1;--k)dp[j][k]=dp[j][k]+dp[j-w[i]][k-1];}}// for(int i=0;i<=cnt;++i)cout<<dp[m][i]<<' ';cout<<"You have "<<dp[m][cnt]<<" selection(s) to buy with "<<cnt<<" kind(s) of souvenirs."<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【01背包的k值问题 HDU2639 HDU2126】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。