Description

　　辰辰是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。” 　　如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

Input

　　輸入文件的第一行包含兩個(gè)正整數(shù)N,M。M表示總共能夠用來采藥的時(shí)間，N代表山洞里的草藥的數(shù)目。接下來的N行每行包括兩個(gè)的整數(shù)，分別表示采摘某株草藥的時(shí)間Ti和這株草藥的價(jià)值Vi。

Output

　　輸出文件僅包含一個(gè)整數(shù)表示規(guī)定時(shí)間內(nèi)可以采到的草藥的最大總價(jià)值。
　　

Data Constraint

50%的數(shù)據(jù)中 N，M ≤ 1000； 100%的數(shù)據(jù)中 N，M ≤ 100000，Ti，Vi ≤10

Analysis

一眼看去是01背包，然而n太大會爆
再看發(fā)現(xiàn)Ti和Vi不超過10，按費(fèi)用分成10類做排序，就變成有10種物品的背包
用數(shù)組記錄狀態(tài)，順推一下就好了
f[i+j]=f[i]+v[j](0≤j≤min(i,10))
就這樣

當(dāng)然還有方法二
10*10種可能，也就是100種不同費(fèi)用、不同價(jià)值的物品，有多個(gè)可以選擇
變成了多重背包
再把多重背包轉(zhuǎn)化成01背包(汗)，速度確實(shí)可以上來

code

#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; int t[11][101001]; int b[100101][11]; int f[100101]; bool cmp(int x,int y){return x>y;} int min(int x,int y){return x<y?x:y;} int main() {int n,m;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){int a,ob;scanf("%d%d",&a,&ob);t[a][++t[a][0]]=ob;}for (int i=1;i<=10;i++)sort(t[i]+1,t[i]+t[i][0]+1,cmp);for (int i=0;i<=m;i++){int v=0,num=0,p=min(i,10);for (int j=1;j<=10;j++)if (b[i][j]<t[j][0]){int k=b[i][j]+1;if (f[i+j]<t[j][k]+f[i]){f[i+j]=t[j][k]+f[i];for (int g=1;g<=10;g++)b[i+j][g]=b[i][g];b[i+j][j]=b[i][j]+1;}}}printf("%d\n",f[m]);return 0; } #include <stdio.h>using namespace std;int map[11][11]; int w[100001],v[100001],f[100001];int max(int x,int y) {return x>y?x:y; }int main() {int n,m,count=0;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);map[x][y]++;}for (int i=1;i<=10;i++)for (int j=1;j<=10;j++){int tmp=0,o=0,k=1;while (k*2<map[i][j]){w[++count]=i*k;v[count]=j*k;o+=k;k*=2;}if (o!=map[i][j]){w[++count]=(map[i][j]-o)*i;v[count]=(map[i][j]-o)*j;}}for (int i=1;i<=count;i++)for (int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]);printf("%d\n",f[m]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/olahiuj/p/5781217.html

總結(jié)

以上是生活随笔為你收集整理的采药2_纪中2540_dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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