1. 首页
  2. 文章中心
  3. 动态规划

背包问题例题总结背包1背包2背包3背包4

90 阅读 0 评论
我是靠谱客的博主 内向红酒，这篇文章主要介绍背包问题例题总结背包1背包2背包3背包4，现在分享给大家，希望可以做个参考。

背包问题之前学了，不过现在又忘得差不多了（可惜之前没有写博客总结），现在结合例题重新复习一下。

例1：

背包1

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

复制代码
1
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过 W 的物品，求所有方案中价值总和的最大值。

Input:

复制代码
1
2
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000）
，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）。

Output:

复制代码
1
输出为一行，即所有方案中价值总和的最大值。

Sample Input:

复制代码
1
2
3
4
3 4
1 2
2 5
3 7

Sample Output:

复制代码
1
9

附上AC代码加解析：

复制代码
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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define long long ll
int dp[1111];//建立一个dp数组，用来储存剩下w重量可用时所拥有的价值最大w,即dp[w] = v
int main()
{
int n,w;
int wi[11111];
int vi[11111];
while(cin >> n >> w)
{
memset(dp,0,sizeof(dp));
for(int i = 0;i < n;i++)
scanf("%d%d",&wi[i],&vi[i]);
for(int i = 0;i < n;i++)//列举出每个物品
for(int j = w;j >= wi[i];j--)//将剩余重量从大到小排列，不能从小到大列举，因为这样会导致一个物品可能被使用多次
dp[j] = max(dp[j],dp[j-wi[i]]+vi[i]);
printf("%dn",dp[w]);
}
return 0;
}



例二：

背包2

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

复制代码
1
2
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量刚好为 W 的物品
，求所有方案中价值总和的最大值。

Input:

复制代码
1
2
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000）
，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）。

Output:

复制代码
1
输出为一行，即所有方案中价值总和的最大值。若不存在刚好填满的情况，输出“-1”。

Sample Input:

复制代码
1
2
3
4
5
6
7
8
3 4
1 2
2 5
2 1
3 4
1 2
2 5
5 1

Sample Output:

复制代码
1
2
6
-1

这题就是上题的改版，附上AC代码：

复制代码
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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define long long ll
int dp[11111];
int main()
{
int n,w;
while(~scanf("%d%d",&n,&w))
{
memset(dp,-1,sizeof(dp));//所有值设置为-1，当dp[i]等于-1时，表示暂时没有出现剩余i重量的情况
dp[0] = 0;//设置一个初始值为0
int wi[n],vi[n];
for(int i = 0;i < n;i++)
scanf("%d%d",&wi[i],&vi[i]);
for(int i = 0;i < n;i++)
for(int j = w;j >= wi[i];j--)
if(dp[j-wi[i]] != -1)
dp[j] = max(dp[j],dp[j-wi[i]]+vi[i]);
printf("%dn",dp[w]);
}
return 0;
}


例3：

背包3

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

复制代码
1
2
有 n 种（每一种有无数个）重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总
量不超过 W 的物品，求所有方案中价值总和的最大值。

Input:

复制代码
1
2
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000）
，接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）

Output:

复制代码
1
输出为一行，即所有方案中价值总和的最大值。

Sample Input:

复制代码
1
2
3
4
5
6
7
8
3 4
1 2
2 5
3 7
3 5
2 3
3 4
4 5

Sample Output:

复制代码
1
2
10
7

这题跟第一题类似，如果理解第一题为什么是把剩余重量从大到小排列，就能理解为什么只要这题从小到大排列即可AC

附上AC代码：

复制代码
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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define long long ll
int dp[11111];
int main()
{
int n,w;
while(~scanf("%d%d",&n,&w))
{
memset(dp,0,sizeof(dp));
int wi[n],vi[n];
for(int i = 0;i < n;i++)
scanf("%d%d",&wi[i],&vi[i]);
for(int i = 0;i < n;i++)
for(int j = wi[i];j <= w;j++)//剩余重量从小到大就能重复利用每个物品，从大到小就只能利用一次
dp[j] = max(dp[j],dp[j-wi[i]]+vi[i]);
printf("%dn",dp[w]);
}
return 0;
}

例4：

背包4

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

复制代码
1
有 n 个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过 W 的物品，求所有方案中价值总和的最大值。

Input:

复制代码
1
2
3
4
5
6
输入包含多组测试用例，每一例的开头为两位整数 n、W;接下来有 n 行，每一行有两位整数 Wi、Vi
其中：
1<=n<=100
1<=W<=1000,000,000
1<=Wi<=10,000,000
1<=Vi<=100。

Output:

复制代码
1
输出为一行，即所有方案中价值总和的最大值。

Sample Input:

复制代码
1
2
3
4
5
6
7
8
9
10
4 5
2 3
1 2
3 4
2 2
4 10000000
2 3
2 2
3 3
1 2

Sample Output:

复制代码
1
2
7
10

这题需要转换下思维，因为按照前面的方法，重量太大，肯定会超时，不过，相对而言，价值却变小了。如果理解了前面几题，并转换了思维，这题应该不难。

附上AC代码：

复制代码
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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define long long ll
int dp[11111];
int main()
{
int n,w;
while(~scanf("%d%d",&n,&w))
{
for(int i = 0;i < 10005;i++)
dp[i] = 1111111111;
dp[0] = 0;
int wi[n],vi[n];
for(int i = 0;i < n;i++)
scanf("%d%d",&wi[i],&vi[i]);
for(int i = 0;i < n;i++)
for(int j = 10005;j >= vi[i];j--)
if(dp[j-vi[i]] != 1111111111 && dp[j-vi[i]]+wi[i] <= w)
dp[j] = min(dp[j],dp[j-vi[i]]+wi[i]);
for(int i = 10004;i >= 0;i--)
if(dp[i] != 1111111111)
{
printf("%dn",i);
break;
}
}
return 0;
}


最后

以上就是内向红酒最近收集整理的关于背包问题例题总结背包1背包2背包3背包4的全部内容，更多相关背包问题例题总结背包1背包2背包3背包4内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(60)

相关文章

PAT 1027 打印沙漏 (20分)（Java）
PAT 1027 打印沙漏 (20分)（Java）
[luoguP1507] NASA的食物计划（DP）
[luoguP1507] NASA的食物计划（DP）
练习题 No.5 背包问题(动态规划-记忆化搜索)
练习题 No.5 背包问题(动态规划-记忆化搜索)
Vijos - NASA的食物计划(背包)
Vijos - NASA的食物计划(背包)
背包问题例题总结背包1背包2背包3背包4
背包问题例题总结背包1背包2背包3背包4
背包问题常见题型
背包问题常见题型
背包问题练习I NEED A OFFER!   HDU   1203Piggy-Bank  HDU 1114开心的金明   洛谷  1060 小A点菜   洛谷  1164采药   洛谷   1048装箱问题   洛谷    1049疯狂的采药   洛谷    1616
背包问题练习I NEED A OFFER!   HDU   1203Piggy-Bank  HDU 1114开心的金明   洛谷  1060 小A点菜   洛谷  1164采药   洛谷   1048装箱问题   洛谷    1049疯狂的采药   洛谷    1616
背包问题题目练习
背包问题题目练习

评论列表共有 0 条评论

立即
投稿
返回
顶部