算法训练- DP问题 - HDU-2602
左边代表骨骼的数量,从0到5,总体积为10,从1排到10,
我们定义一个二维数组m[ i ][ j ] i表示第i个骨骼,j表示背包容量为j;
用0-1背包的问题来求解,就是要得到每一步的最优解,此时第i个物品面临选择,首先我们要看容量是否大于它的重量,
即 j > w[ i ]. 如果大于,我们可以选择拿或不拿
1:拿,那么就必须要占用当前背包的空间。即用当前背包总容量 j - w[ i ],再占用1个物品空间,所以i-1,此时的总价值就是m [ i-1 ] [ j-w[ i ] ] 的解 + 当前的价值v[ i ] ,得到的就是放入当前物品得到的最优解。
2:不拿,那么就还是上一步的解,m[ i-1 ][ j ]
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long LL;
int T;
int n,V;
int w[1001];
int v[1001];
int s[1001][1001];
int main(){
cin>>T;
for(int m=0;m<T;m++){
cin>>n>>V;
memset(s,0,sizeof(s));
for(int j=1;j<=n;j++){
cin>>w[j];
}
for(int j=1;j<=n;j++){
cin>>v[j];
}
int max_wei=0;
//dp
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
if(j>=v[i]){
s[i][j]=max(s[i-1][j],s[i-1][j-v[i]]+w[i]);
}else {
s[i][j]=s[i-1][j];
}
}
}
cout<<s[n][V]<<endl;
}
return 0;
}