來源hdu2602

問題描述

許多年前，在泰迪的家鄉(xiāng)，有一個(gè)人被稱為“骨頭收藏家”。這個(gè)男人喜歡收集各種各樣的骨頭，比如狗狗，牛，還有他去了墳?zāi)?.....
骨頭收藏家有一個(gè)大容量的V袋，沿著他的收集之旅有很多骨頭，顯然，不同的骨骼具有不同的值和不同的體積，現(xiàn)在根據(jù)他的行程給出每個(gè)骨骼的值，你能計(jì)算出骨骼采集器可以得到的總值的最大值嗎？

輸入

第一行包含整數(shù)T，個(gè)案數(shù)。
接下來是T個(gè)案例，每個(gè)案例有三行，第一行包含兩個(gè)整數(shù)N，V，（N <= 1000，V <= 1000）表示骨骼的數(shù)量和他的包的體積。第二行包含表示每個(gè)骨骼值的N個(gè)整數(shù)。第三行包含表示每個(gè)骨骼體積的N個(gè)整數(shù)。

輸出

每行一個(gè)整數(shù)表示總值的最大值（此數(shù)字將小于2 31）。

樣本輸入

1
5 10
1 2 3 4 5
5 4 3 2 1

樣本輸出

14

最基礎(chǔ)01背包，判斷第i件要不要放進(jìn)去，狀態(tài)轉(zhuǎn)移方程dp[i][V]=max{dp[i-1][V],dp[i-1][V-v[i]]+w[i]}

“將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。

#include<iostream> #include<stdio.h> #include<stdlib.h> #include <iomanip> #include<cmath> #include<float.h> #include<string.h> #include<algorithm> #define sf scanf #define pf printf #define scf(x) scanf("%d",&x) #define scff(x,y) scanf("%d%d",&x,&y) #define prf(x) printf("%d\n",x) #define mm(x,b) memset((x),(b),sizeof(x)) #include<vector> #include<queue> #include<map> #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=a;i>=n;i--) typedef long long ll; const ll mod=1e9+100; const double eps=1e-8; using namespace std; const double pi=acos(-1.0); const int N=1005; int dp[N][N]; int w[N],v[N]; int main() {int re,V,n;scf(re);v[0]=0;w[0]=0;while(re--){mm(dp,INT_MIN);scff(n,V);rep(i,1,n+1)scf(w[i]);rep(i,1,n+1)scf(v[i]);rep(i,1,n+1)//第i件物品 rep(j,0,V)//空間為j的時(shí)候 {if(v[i]<=j)dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);elsedp[i][j]=dp[i-1][j];}prf(dp[n][V]);}return 0; }

一維

#include<iostream> #include<stdio.h> #include<stdlib.h> #include <iomanip> #include<cmath> #include<float.h> #include<string.h> #include<algorithm> #define sf scanf #define pf printf #define scf(x) scanf("%d",&x) #define scff(x,y) scanf("%d%d",&x,&y) #define prf(x) printf("%d\n",x) #define mm(x,b) memset((x),(b),sizeof(x)) #include<vector> #include<queue> #include<map> #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=a;i>=n;i--) typedef long long ll; const ll mod=1e9+100; const double eps=1e-8; using namespace std; const double pi=acos(-1.0); const int N=1e3+5; int dp[N]; int w[N],v[N]; int main() {int re,V,n;scf(re);while(re--){mm(dp,0);scff(n,V);rep(i,1,n+1)scf(w[i]);rep(i,1,n+1)scf(v[i]);rep(i,1,n+1){per(j,V,v[i])dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}prf(dp[V]);}return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的骨骼收集器01背包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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