思路
所有的动态规划题都可以写成递归版本,递归版本更方便理解,当然递归调用可能会超时。
动态规划的核心是将原问题转化为更容易求解的子问题,进而找出最优子结构。
对于这道题来说,我们令OPT(k,V)表示从前k件物品中选出体积不超过V的最大价值,那么对于第k个件物品,自然有两种情况,
1. 选第k件, OPT(k-1, V-v[k])+w[k], 这表示从前k-1件物品中选出,不超过(V-v[k])体积的物品,然后其价值加上第k件;
2. 不选第k件, OPT(k-1, V)
因为我们要的是最优子结构,所以要从选第k件和不选第k件中选择最大的。
故而最优子结构为:
OPT(k, V) = max{ OPT(k-1, V-v[k])+w[k], OPT(k-1, V)}
所以我们就可递归的进行求解了。
但是正常递归会超时,因为我们对于这个问题的递归树的很多叶子节点进行了重复计算。
那么怎么解决这种重复计算呢,就是以存代算,假设用一个叫mem的数组存了之前的结果
那么就可以有如下的过程:
if OPT(k, V) 已经计算过:
return mem[k,V]
else:
if V >= v[k]: # 需要能装得下第k件物品
mem[k,V] = max(
OPT(k-1, V), # 不选第k件
OPT(k-1, V-v[k]) + w[k] # 选第k件
)
else:
mem[k,V] = OPT(k-1, V)
return mem[k, V]
当然还要注意一些边界的处理,就不过多赘述了,具体看代码中怎么实现吧。
代码c++
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1010;
int opt[MAX][MAX];
int w[MAX], v[MAX];
int dp(int k,int V){
// cout<<"call opt("<<k<<","<<V<<")"<<endl;
if (opt[k][V]!=-1){
return opt[k][V];
}
if (V>=v[k])
opt[k][V] = max(dp(k-1,V), dp(k-1, V-v[k])+w[k]);
else
opt[k][V] = dp(k-1,V);
return opt[k][V];
}
int main(){
int N,V;
cin>>N>>V;
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
for (int i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
opt[i][j] = -1;
for (int i=0;i<=V;i++)
opt[0][i] = 0;
cout<<dp(N,V)<<endl;
return 0;
}