分析
与01背包很类似,只不过现在不限制第k件选了几次了,所以一种朴素的方法就是枚举所有可能的次数m:
OPT(k, V) = MAX{
OPT(k-1, V), 不选
OPT(k-1 ,V-mv[i])+mw[i] 选择m个第k个物品
}
然而,不幸的是这样的枚举最终只能过14/16个算例,最后两个算例会报TLE(与是否递归无关,就算不用递归的方法也会TLE)。
那么其实这个循环耗费了很多时间,如果可以将循环省去就好了。
令OPT(k, V, m)表示从1,2,3…k个物品中选出不超过V的体积,最大的价值量为OPT(k, V, m),其中m是第k个物品选了m次。
那么,有
OPT(k, V) = max{OPT(k, V, m) | m = 1,2,3…}
OPT(k, V, m) = max{OPT(k, V, m-1), OPT(k, V-v[i],m-1)+w[i]}
那么其实选择m个第k件物品也可以在OPT(k, V)的只依赖选择了m-1个第k件物品时候的最优解。所以m就可以省去,整合起来就是
1. OPT(k, V) = OPT(k-1, V) 每次先初始化为前一个状态的最优解
2. OPT(k, V) = max{OPT(k, V}, OPT(k, V-v[i])+w[i]} 这里需要循环所有可能的V,代表的是选择几个第k个物品
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1010;
int w[MAX], v[MAX];
int OPT[MAX][MAX];
/**
* 最优结构,前k个商品中,不超过体积V的最大价值
* OPT(k, V) = MAX{
* OPT(k-1, V), 不选
* OPT(k-1 ,V-m*v[i])+m*w[i] 选择m个第k个物品
* }
**/
// 递归版
int dp(int k, int c) {
if (OPT[k][c]!=-1)
return OPT[k][c];
OPT[k][c] = dp(k-1,c);
if (c>=v[k])
OPT[k][c] = max(dp(k,c), dp(k, c- v[k]) + w[k]);
return OPT[k][c];
}
// 不用递归版
// int dp(int n, int c){
// for(int i=1;i<=n;i++){
// for (int j=0;j<=c;j++){
// OPT[i][j] = OPT[i-1][j];
// if(j>=v[i])
// OPT[i][j] = max(OPT[i][j], OPT[i][j-v[i]]+w[i]);
// }
// }
// return OPT[n][c];
// }
int main(){
int N,V;
cin>>N>>V;
for(int i=1;i<=N;i++)
cin>>v[i]>>w[i];
for (int i=1;i<=N;i++)
for(int j=1;j<=V;j++)
OPT[i][j] = -1;
cout<<dp(N,V)<<endl;
return 0;
}