whelve

3725

qilin02811

tigerchen

sep
21KINGDMG
yxc

capper

SKG_G

cymzq
LINNO

whelve
2天前

# 动态规划 - 闫式DP分析法

## 背包问题

1、 01背包

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w);
2、完全背包

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, ... );
f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ... );
f[i][j] = max(f[i - 1][j], f[i][j - v] + w);


3、多重背包

for (int k = 1; k <= s && k * v <= j; k ++ );

whelve
2天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 510;
int V1, V2, n, v1, v2;
int f[N][M];

{int main()

cin >> V1 >> V2 >> n;
for (int i = 0; i < n; i ++ )
{
cin >> v1 >> v2;
for (int j = V1; j >= v1; j -- )
for (int k = V2 - 1; k >= v2; k -- )
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
cout << f[V1][V2 - 1] << ' ';
int k = V2 - 1;
while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k -- ;
cout << V2 - k << endl;

return 0;
}


whelve
3天前
#include <iostream>
using namespace std;
const int N = 20005;
int n, m, v;
int f[N];

int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
cin >> v;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + v);
}
cout << m - f[m] << endl;

return 0;
}


whelve
3天前
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, v, w;
int f[N];

int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
cin >> v >> w;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;

return 0;
}


whelve
5天前

whelve
14天前

whelve
19天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ )
{
int maxv = 1;
for (int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}


whelve
21天前
http://139.196.8.108:8000/


whelve
21天前
http://139.196.8.108:8000/


whelve
26天前
n = int(input())
path = [0 for i in range(n)]
used = [False for i in range(n)]

def dfs(u):
if u == n:
for i in range(n):
print(path[i] + 1, end = ' ')
print()
else:
for i in range(n):
if not used[i]:
path[u] = i
used[i] = True
dfs(u + 1)
used[i] = False
path[u] = 0
dfs(0)