蓝桥杯 小明的背包1 小兰的神秘礼物 01背包问题 模板 C++
01背包问题
问题描述
n件物品，一个容量是m的背包。每件物品只能使用一次。
第i个物品的体积是w[i],价值是v[i]。
求解将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大。
算法思路
共有两种求解方法(二维数组和一维数组),推荐选择一维数组。
1、二维数组
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j<w[i])//装不下第i个物品,价值与第i-1个物品相等
{
f[i][j]=f[i-1][j];
}else{//如果能装下,进行抉择是否选择第i个物品
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
cout<<f[n][m];
2、一维数组(推荐)
for(int i=1;i<=n;i++)
{
int w,v;
cin>>w>>v;
for(int j=m;j>=w;j--)
{
f[j]=max(f[j],f[j-w]+v);
}
}
cout<<f[m];
实战1-小明的背包1
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 件物品，第i件物品的体积为wi，价值为 vi。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第2~N+1行包含 2 个正整数 w,v，表示物品的体积和价值。
1 ≤ N≤ 102, 1≤ V ≤ 103, 1 ≤ wi, vi ≤ 103
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 20
1 6
2 5
3 8
5 15
3 3
输出
37
完整代码
1、二维数组
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int w[N],v[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i]>>v[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j<w[i]){f[i][j]=f[i-1][j];}else{f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);}}}cout<<f[n][m];return 0;
}2、一维数组
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int w,v;cin>>w>>v;for(int j=m;j>=w;j--){f[j]=max(f[j],f[j-w]+v);}}cout<<f[m];return 0;
}实战2-小兰的神秘礼物
问题描述
小兰要过生日了，好朋友妮妮想送她一个特别的礼物。妮妮找来了一个神秘的箱子，箱子的容量为 V。她还收集了 n 个有趣的小物件，每个物件都有一个体积 。
妮妮想把这些小物件中的一部分装进箱子里，当然也可以一个都不装。但是，为了增加神秘感，她希望箱子装得尽可能满，剩余的空间最小。你能帮妮妮计划一下，让她知道箱子最终的最小剩余空间吗?
输入格式
第一行共一个整数 V，表示箱子的容量。
第二行共一个整数 n，表示收集的小物件总数。
接下来的 几 行，每行包含一个正整数 ~，表示第之个小物件的体积。
数据范围保证:0<n<1000，1<x,V<1000.
输出格式
输出一个整数，表示箱子的最小剩余空间。
样例输入
300
3
120
260
190
样例输出
40
完整代码
1、二维数组
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int w[N];
int main()
{int n,m;cin>>m>>n;for(int i=1;i<=n;i++){cin>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j<w[i]){f[i][j]=f[i-1][j];}else{f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+w[i]);//将体积当做价值 }}}cout<<m-f[n][m];return 0;
}2、一维数组
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int main()
{int m;cin>>m;int n;cin>>n;for(int i=1;i<=n;i++){int w;cin>>w;for(int j=m;j>=w;j--){f[j]=max(f[j],f[j-w]+w);//将体积当做价值 }}cout<<m-f[m];return 0;
}