題意：給出包裹的大小v，然后給出n塊骨頭的價值value和體積volume，求出一路下來包裹可以攜帶骨頭最大價值

思路：01背包

1.二維數組（不常用

#include<iostream> #include<stdio.h> #include<math.h> using namespace std; int dp[1100][1100]; int main() {int i,j;int t,n,_v;//測試用例個數，物品種類，背包大小int c[1100],v[1100];//花費，價值scanf("%d",&t);while(t--){scanf("%d%d",&n,&_v);for(j=0; j<=_v; ++j)dp[0][j]=0;for(i=1; i<=n; ++i)scanf("%d",&v[i]);for(i=1; i<=n; ++i)scanf("%d",&c[i]);for(i=1; i<=n; ++i){for(j=0; j<c[i]; ++j)dp[i][j]=dp[i-1][j];for(j=c[i]; j<=_v; ++j){if(dp[i-1][j-c[i]]+v[i]>dp[i-1][j])dp[i][j]=dp[i-1][j-c[i]]+v[i];else dp[i][j]=dp[i-1][j];}}printf("%d\n",dp[n][_v]);}return 0; } View Code

2.一維數組（之后 多重、完全背包 的解法 皆采用一維數組）

1...n
?? _v...0

#include<iostream> #include<stdio.h> using namespace std; int dp[1100]; int main() {int i,j;int t,n,_v;//測試用例個數，物品種類，背包大小int c[1100],v[1100];//花費，價值scanf("%d",&t);while(t--){scanf("%d%d",&n,&_v);for(j=0; j<=_v; ++j)dp[j]=0;for(i=1; i<=n; ++i)scanf("%d",&v[i]);for(i=1; i<=n; ++i)scanf("%d",&c[i]);for(i=1; i<=n; ++i)for(j=_v; j>=c[i]; --j)if(dp[j-c[i]]+v[i]>dp[j])dp[j]=dp[j-c[i]]+v[i];printf("%d\n",dp[_v]);}return 0; } View Code

?附一道01背包好題：http://acm.csu.edu.cn/OnlineJudge/problem.php?cid=2071&pid=0

轉載于:https://www.cnblogs.com/bofengyu/p/4739277.html

總結

以上是生活随笔為你收集整理的hdu 2602 Bone Collector（01背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

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