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

例1：

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

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

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

3 4
1 2
2 5
3 7

9

附上AC代码加解析：

#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;
}

例二：

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

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

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

3 4
1 2
2 5
2 1
3 4
1 2
2 5
5 1

6
-1

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

#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：

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

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

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

3 4
1 2
2 5
3 7
3 5
2 3
3 4
4 5

10
7

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

附上AC代码：

#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：

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

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

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

4 5
2 3
1 2
3 4
2 2
4 10000000
2 3
2 2
3 3
1 2

7
10

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

附上AC代码：

#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所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。