动态规划
01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,V;
cin>>n>>V;
vector<int>bag(V+1);
vector<int>w(n+1);
vector<int>v(n+1);
for(int i=0;i<n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=0;i<n;i++)
{
for(int j=V;j>=v[i];j--)
{
if(bag[j]<bag[j-v[i]]+w[i])
bag[j]=bag[j-v[i]]+w[i];
}
}
cout<<bag[V]<<"\n";
}
return 0;
}
|
当背包容量特别大时可以总价值为数组长度，求获得每个价值所需最小容量；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n;
ll V;
cin>>n>>V;
vector<int>w(n+1);
vector<ll>v(n+1);
ll sum=0;
for(int i=0; i<n; i++)
{
cin>>v[i]>>w[i];
sum+=w[i];
}
vector<ll>dp(sum+1,1e12+1);
dp[0]=0;
for(int i=0; i<n; i++)
for(int j=sum; j>=w[i]; j--)
if(dp[j]>dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
for(int i = sum; i>=0; i--)
if(dp[i]<=V)
{
cout<<i<<"\n";
return 0;
}
}
|
完全背包
可以通过价值来预处理去掉一些物品；
与01只有v遍历顺序不同；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,V;
cin>>n>>V;
vector<int>bag(V+1);
vector<int>w(n+1);
vector<int>v(n+1);
for(int i=0;i<n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=V;j++)
{
if(bag[j]<bag[j-v[i]]+w[i])
bag[j]=bag[j-v[i]]+w[i];
}
}
cout<<bag[V]<<"\n";
}
return 0;
}
|
可以转化为01背包(每种物品最多多少件)，之后根据二进制思想拆开；(多重背包)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n,V;
cin>>n>>V;
vector<pair<int,int>>all;
for(int i=0; i<n; i++)
{
int k,v,w;
cin>>k>>v>>w;
int mid=1;
while(mid<=k)
{
all.push_back({v*mid,w*mid});
k-=mid;
mid*=2;
}
if(k>0)
all.push_back({v*k,w*k});
}
vector<ll>bag(V+1,0);
n=all.size();
for(int i=0; i<n; i++)
for(int j=V; j>=all[i].first; j--)
if(bag[j]<bag[j-all[i].first]+all[i].second)
bag[j]=bag[j-all[i].first]+all[i].second;
cout<<bag[V]<<"\n";
}
return 0;
}
|
分组背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <iostream>
#include <vector>
using namespace std;
int f[101];
int main()
{
int N, V, S;
cin >> N >> V;
vector<vector<int>> weights(N + 1, vector<int>{0});
vector<vector<int>> values(N + 1, vector<int>{0});
for (int i = 1; i <= N; i++)
{
cin >> S;
for (int j = 0; j < S; j++)
{
int weight, value;
cin >> weight >> value;
weights[i].push_back(weight);
values[i].push_back(value);
}
}
for (int i = 1; i <= N; i++)
{
for (int j = V; j >= 0; j--)
{
for (int k = 1; k < weights[i].size(); k++)
{
if (j >= weights[i][k])
f[j] = max(f[j], f[j - weights[i][k]] + values[i][k]);
}
}
}
cout << f[V] << endl;
return 0;
}
|
求具体方案
总价值最大，输出字典序最小的方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
#include <vector>
using namespace std;
int f[1005][1005];
int main()
{
int N, V;
cin >> N >> V;
vector<int> weights(N + 1, 0);
vector<int> values(N + 1, 0);
for (int i = 1; i <= N; i++)
{
cin >> weights[i] >> values[i];
}
for (int i = N; i > 0; i--)
{
for (int j = 0; j <= V; j++)
{
if (j >= weights[i])
f[i][j] = max(f[i + 1][j], f[i + 1][j - weights[i]] + values[i]);
else
f[i][j] = f[i + 1][j];
}
}
vector<int> conditions(N + 1, 0);
int curN = 1;
int curV = V;
while (curN <= N)
{
if (curV >= weights[curN] && f[curN][curV] == f[curN + 1][curV - weights[curN]] + values[curN])
{
conditions[curN] = 1;
curV -= weights[curN];
}
else if (f[curN][curV] == f[curN + 1][curV])
{
conditions[curN] = 0;
}
curN++;
}
for (int i = 1; i <= N; i++)
if (conditions[i])
cout << i << " ";
return 0;
}
|
最优方案数
这里为取模后的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <vector>
using namespace std;
#define mod 1000000007
int f[1001];
int nums[1001];
int main()
{
int N, V;
cin >> N >> V;
vector<int> weights(N + 1, 0);
vector<int> values(N + 1, 0);
for (int i = 1; i <= N; i++)
{
cin >> weights[i] >> values[i];
}
for (int i = 0; i <= V; i++)
nums[i] = 1;
for (int i = 1; i <= N; i++)
{
for (int j = V; j >= 0; j--)
{
if (j < weights[i])
continue;
if (f[j - weights[i]] + values[i] == f[j])
{
nums[j] = (nums[j] + nums[j - weights[i]]) % mod;
}
else if (f[j - weights[i]] + values[i] > f[j])
{
nums[j] = nums[j - weights[i]];
}
f[j] = max(f[j], f[j - weights[i]] + values[i]);
}
}
cout << nums[V] << endl;
return 0;
}
|
