蒜头君的购物袋123集(背包问题)---你害我好惨
首先贴个大佬整理的背包九讲github链接
下面是这个题目的代码
题目1:
蒜头君去超市购物，他有一只容量为 V 的购物袋，同时他买了 n件物品，已知每件物品的体积 vi。蒜头君想知道，挑选哪些物品放入购物袋中，可以使袋子剩余的空间最小。
输入格式
第一行输入一个整数 V（1≤V≤20,000），表示购物袋的容量。
第二行输入一个整数 n（1≤n≤30），表示蒜头君购买的n件物品。
接下来输入n行，每行输入一个整数 vi（1≤vi≤10,000），表示第i件物品的体积。
输出格式
输出一行，输出一个整数，表示购物袋最小的剩余空间。
样例输入
20
5
7
5
7
3
7
样例输出
点我!
#include
using namespace std;
int dp[31][20001]; //于是我们使dp[i]代表在第1~i编号中j容量的袋子可放下最大物品体积。
int main()
{
int v, n;
cin >> v >> n;
int ti[31];
for (int i = 1; i <= n; i++)
cin >> ti[i];
for (int i = 1; i <= n; i++)//对全体依次判断装袋
{
for (int j = 1; j <= v; j++)//容量变化,取到最优
{
if (ti[i] > j)//当前容量装不下
dp[i][j] = dp[i - 1][j];//放不下(记为与不装第i物品时,容量为j的容器能装的最大体积)
else
dp[i][j] = max(dp[i - 1][j - ti[i]] + ti[i], dp[i - 1][j]);//当j>=shop[i]时，可以放，也可以不放。
}//要放,就拿前一个(j-ti[i]---保证装入后总体积恰好为j)最佳情况的最大体积加上当次的物品体积
}
cout << v - dp[n][v];
}
题目2:
蒜头君去超市购物，他有一只容量为V的购物袋，同时他想买n件物品，已知每件物品的体积 vi和重要度pi ?。
蒜头君想知道，挑选哪些物品放入购物袋中，可以使得买到的物品重要度之和最大，且物品体积和不超过购物袋的容量。(01背包)
输入格式
第一行输入两个整数V（1≤V≤1000）和n（1≤n≤100）。代表购物袋的总体积为V，蒜头君一共想买n件物品。
接下来输入n 行，每行输入两个整数 vi? 和 pi?（1≤vi,pi≤100），分别表示每件物品的体积和重要度。
输出格式
输出一行，输出一个整数，表示蒜头君能买到物品的最大重要度之和。
样例输入
50 4
1 5
60 99
49 8
33 7
样例输出
13
点鸡
#include
using namespace std;
int dp[1001][10001];//dp[i][j],表示第i件物品时,容量为j容器,装的最大重要度
int main()
{
int v, n;
cin >> v >> n;
int ti[1001];
int p[1001];
for (int i = 1; i <= n; i++)
cin >> ti[i] >> p[i];
for (int i = 1; i <=n; i++) //对全体依次判断装袋
{
for (int j = 0; j <= v; j++) //容量变化,不超范围
{
if (ti[i] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j - ti[i]] + p[i], dp[i - 1][j]);//前作是取到加体积,本作是取到加重要度.
}
}
cout << dp[n][v];
}
题目3:
问题描述
蒜头君去超市购物，他有一只容量为 V 的购物袋，同时他想买 nn 种物品，已知每种物品的体积 vi和重要度 pi 。蒜头君想知道，怎么挑选物品放入购物袋中，可以使得买到的物品重要度之和最大，且物品体积和不超过购物袋的容量。注意超市中每种物品的数量无限多。(完全背包)
输入格式
第一行输入两个整数 n, V (1≤n≤1,000,1≤V≤10,000)。
接下来输入 n 行，每行输入两个整数 vi和pi(1≤vi,pi≤10,000)，分别表示第 i 种物品的体积和重要度。
输出格式
输出一行，输出一个整数，表示能买到物品的最大重要度之和。
样例输入
4 20
3 7
2 5
4 6
5 9
样例输出
50
点开吧
#include
using namespace std;
int p[1050];
int vi[1050];
int dp[10050]; //dp[i]指容量为i时的最大重要度
int main()
{
int v, n;
cin >> n >> v;
for (int i = 1; i <= n; i++)
{
cin >> vi[i] >> p[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = vi[i]; j <= v; j++)//每个物品从能装下开始判断
{
dp[j] = max(dp[j - vi[i]] + p[i], dp[j]);//在合适情况下,可以实现多次累加(dp[j]=0时没有记录)
}
}
cout << dp[v];
return 0;
}
ps:1.这次尝试用md编写了博客 2.感觉自己对背包还是不太懂啊