本文主要是介绍HDU2602（01背包复习），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602
突然想到自己虽然复习了dp，但是01背包和完全背包问题，居然没有做点OJ题，有点说不过去啊。
这个就是01背包模板题，就是体积V的包去装骨头，每个骨头有价值value和体积volume。
先来个二维的01背包
dp[i][j]:表示从0到i-1这i个物品中选出总重量不超过j的物品时总价值的最大值。
递推公式如下：
内层j循环反过来也是一样的。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define N 1005
int Value[N],Volume[N],dp[N][N];
int main(){int t,n,v;cin>>t;while(t--){cin>>n>>v;mem(dp,0);for(int i=0;i<n;i++){cin>>Value[i];}for(int i=0;i<n;i++){cin>>Volume[i];}for(int i=0;i<n;i++){for(int j=0;j<=v;j++){if(j<Volume[i]){dp[i+1][j]=dp[i][j];}else{dp[i+1][j]=max(dp[i][j],dp[i][j-Volume[i]]+Value[i]);}}}cout<<dp[n][v]<<endl;}return 0;
}一维背包
记住内层循环是从j=V开始的，因为那是从二维dp简化而来的，如果从volume[i]开始，那样同一样东西就会拿重复了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define N 1005
int Value[N],Volume[N],dp[N];
int main(){int t,n,v;cin>>t;while(t--){cin>>n>>v;mem(dp,0);for(int i=0;i<n;i++){cin>>Value[i];}for(int i=0;i<n;i++){cin>>Volume[i];}for(int i=0;i<n;i++){for(int j=v;j>=Volume[i];j--){dp[j]=max(dp[j],dp[j-Volume[i]]+Value[i]);}}cout<<dp[v]<<endl;}return 0;
}
这篇关于HDU2602（01背包复习）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
