有 N 件物品和一个容量为 C 的背包, 第 i 件物品的费用是 c[i], 价值是 w[i], 求将若干件物品放入背包所能够获得的最大价值.
每种物品只有一件, 可以选择放或者是不放
使用 f(i,v) 表示前 i 件物品恰好放入一个容量为 v 的背包所能获得的最大价值
状态转移方程:
f(i,v)=max{f(i-1,v),f(i-1,v-c[i])+w[i]}
时间复杂度为 O(N*V), 空间复杂度可以优化为 O(V), 即采用滚动数组的形式, 与完全背包的实现相比较, 这里是逆推, 完全背包是正推
f(v)=max{f(v),f(v-c[i])+w[i]}
首先我们给出第一个状态转移方程的实现:
- int f[maxn][maxv];
- int ans=0;
- void dp()
- {
- for(int i=1;i<=N;i++)
- for(int j=1;j<=V;j++)
- {
- if(v[i]<=j)
- f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
- else
- f[i][j]=f[i-1][j];
- }
- ans=f[N][V];
- }
可以看到循环变量是很好写的
接下来我们给出滚动数组形式转移方程的实现:
- int f2[maxv];
- void dp2()
- {
- for(int i=1;i<=N;i++)
- for(int j=V;j>=0;j--)
- {
- if(v[i]<=j)
- f2[j]=max(f2[j],f2[j-v[i]]+w[i]);
- }
- ans=f2[V];
- }
这种方法虽然省空间, 但是中间结果都被覆盖掉了
最后我们给出一个完整的代码:
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int maxn=1005;
- const int maxv=1005;
- int N,V;
- int v[maxn],w[maxn];
- int f[maxn][maxv];
- int ans=0;
- void dp()
- {
- for(int i=1;i<=N;i++)
- for(int j=1;j<=V;j++)
- {
- if(v[i]<=j)
- f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
- else
- f[i][j]=f[i-1][j];
- }
- ans=f[N][V];
- }
- int f2[maxv];
- void dp2()
- {
- for(int i=1;i<=N;i++)
- for(int j=V;j>=0;j--)
- {
- if(v[i]<=j)
- f2[j]=max(f2[j],f2[j-v[i]]+w[i]);
- }
- ans=f2[V];
- }
- int main()
- {
- cin>>V>>N;
- for(int i=1;i<=N;i++)
- cin>>v[i]>>w[i];
- dp2();
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2684618.html