题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//完全背包问题
#include<iostream>
using namespace std;
int dp[2000];
int w[10000];
int v[19999];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
//o(n*n*n)
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++) //因为用的是i 需要j-v[i]这一项已经被更新所以是正序枚举
{
/*for(int k=1;j-k*v[i]>=0;k++) //会超时
dp[j] = max(dp[j],dp[j-k*v[i]] + k*w[i]);//选k件
*/
/*dp[i][j] = dp[i-1][j] , dp[i-1][j-v[i]] + w, dp[i-1][j-2*v[i]] + 2w;
dp[i][j-v] = dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w
*/
/*if(j>=v[i])
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i]); //优化版本--根据上面的递推式
else
dp[i][j] = dp[i-1][j];
*/
//一维优化
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<dp[m];
}