hdu2602 Bone Collector 01背包問題

2019-11-08 02:56:56

字體：大中小

來源：轉載

供稿：網友

題目大意：給出骨頭的價值和重量，用體積為V的背包裝這些骨頭，求最大價值

大致思路：這里為01背包的講解 http://blog.csdn.net/Remilitarize/article/details/55666889

C：（二維數組）

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010;int value[maxn],weight[maxn];int dp[maxn][maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ while(n--){ int a,b,i,j; scanf("%d%d",&a,&b); //a為骨頭數量，b為背包容量 memset(dp,0,sizeof(dp)); //初始化 for(i=1;i<=a;i++) scanf("%d",&value[i]); for(i=1;i<=a;i++) scanf("%d",&weight[i]); for(i=1;i<=a;i++) //選取第i個骨頭 for(j=0;j<=b;j++) //當前背包容量為j if(j>=weight[i]) //如果第i個骨頭能夠裝入背包 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); /*不裝骨頭為dp[i-1][j]，裝骨頭為把第i個骨頭的重量去掉對應容量的dp[i-1][j-weight[i]并加上這個骨頭的價值value[i]*/ else dp[i][j]=dp[i-1][j]; C：（一維數組）

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010;int value[maxn],weight[maxn];int dp[maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ while(n--){ int a,b,i,j; scanf("%d%d",&a,&b); memset(dp,0,sizeof(dp)); for(i=1;i<=a;i++) scanf("%d",&value[i]); for(i=1;i<=a;i++) scanf("%d",&weight[i]); for(i=1;i<=a;i++) for(j=b;j>=weight[i];j--) //注意要從后向前 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); printf("%d/n",dp[b]); } } return 0;}