Description

Rabbit成功地打開了大門后，沒多久就見到了夢寐以求的寶藏。里面的寶石種類共有N 種，每一種都有一個體積v 和它的價值val 。(已知第i 種寶石的體積為i ,編號從1 ~N )更讓Rabbit興奮的是，每種寶石的數量還是無窮無盡的。
Rabbit當然想把所有寶石全都帶回家，但是她帶的袋子卻最多只能裝下總體積為V 的寶石，所以貪心的Rabbit決定要帶走總體積恰好為V 的寶石。
現在她突然想知道自己在拿走寶石數量恰好為N 的情況下總價值最大為多少？

Input

輸入數據第一行是一個正整數T ，表示數據組數。(T<=20 )
每組數據占兩行。
第一行為兩個整數N，V 。(0<N<=1000，N<=V<=min(N?N，2?N) )
接下來一行有N個整數，代表N種寶石的價值vali 。(0<vali<=10000 )

Output

每組測試數據輸出一行，代表在滿足拿走寶石總體積恰為V 和數量恰好為N 的情況下Rabbit能拿走寶石的最大總價值。

Sample Input

1

3 5

6 2 4

Sample Output

16

C++版本一

#include<queue> #include<stack> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; int dp[2001][2001]; int dis[2001][2001]; int w[2001]; int v[2001]; int main() {int n,c,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&c);int i,j;memset(dp,0,sizeof(dp));memset(dis,0,sizeof(dis));for(i=1; i<=n; i++){scanf("%d",&w[i]);v[i]=i;}for(i=1; i<=n; i++){for(j=0; j<=c; j++){for(int k=0; k*v[i]<=j&&k<=n; k++){if(dis[i][j]+k<=n){dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);dis[i][j]+=k;}}}}printf("%d\n",dp[n][c]);}return 0; }

C++版本二

#include<queue> #include<stack> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; int dp[2001]; int dis[2001]; int w[2001]; int v[2001]; int main() {int n,c,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&c);int i,j;memset(dp,0,sizeof(dp));memset(dis,0,sizeof(dis));for(i=1; i<=n; i++){scanf("%d",&w[i]);v[i]=i;}for(i=1;i<=n;i++){for(j=v[i];j<=c;j++){if(dis[i]+1<=n){dis[i]+=1;dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}}printf("%d\n",dp[c]);}return 0; }

?

以上都是錯解

因為個數的限制我們數組再加一維

#include<queue> #include<stack> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; int dp[1010][2001]; int dis[2001]; int w[2001]; int v[2001]; int main() {int n,c,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&c);int i,j;memset(dp,0,sizeof(dp));memset(dis,0,sizeof(dis));for(i=1; i<=n; i++){scanf("%d",&w[i]);v[i]=i;}for(i=1;i<=n;i++){for(j=v[i];j<=c;j++){if(dis[i]+1<=n){dis[i]+=1;dp[dis[i]][j]=max(dp[dis[i]-1][j],dp[dis[i]-1][j-v[i]]+w[i]);}}}printf("%d\n",dp[n][c]);}return 0; }

?

總結

以上是生活随笔為你收集整理的Rabbit寻宝记(2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。