题目描述
经典的01背包问题
算法1
(动态规划) $O(n^2)$
时间复杂度(n*n)
注意事项
1,对于二维和一维的理解
2,状态转移方程:f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int f[maxn];
int v[maxn];
int w[maxn];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i];
cin>>w[i];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]);
return 0;
}