题目描述
blablabla
样例
blablabla
算法1
(dp) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1006;
int f[N][N];
struct bag1
{
int v;
int w;
};
int main()
{
int n , m;
bag1 bag[N];
cin >> n >> m;
for(int i = 1;i <= n; i ++)
cin >> bag[i].v >> bag[i].w;
f[1][1] = 1;
for(int i = 1;i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j]; //考虑到j可能会小于当前物品的体积,所以就先给f[i][j]赋上左半边一定存在的值
if(j >= bag[i].v)
f[i][j] = max(f[i][j] , f[i-1][j-bag[i].v]+bag[i].w);
}
cout << f[n][m];
return 0;
}
算法2
(优化后的dp) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1006;
int f[N];
struct bag1
{
int v;
int w;
};
int main() //dp代码的所有优化都是对代码做等价变形,和问题本身没有关系
{
int n , m;
bag1 bag[N];
cin >> n >> m;
for(int i = 1;i <= n; i ++)
cin >> bag[i].v >> bag[i].w;
for(int i = 1;i <= n; i ++)
for(int j = m; j >= bag[i].v; j --)
f[j] = max(f[j] , f[j-bag[i].v] + bag[i].w); //优化之后若j还是从小到大循环,f[j - v]就会先算出来,f[j]就等价于f[i][j]
//我们要的是f[i - 1][j],就得在没算出来f[j - vi]之前算f[j]
//这样用的f[j] 就是上一层的还没更新的值
cout << f[n][m];
return 0;
}