title: 动态规划_背包问题
date: 2018-07-30 20:36:18
tags:
- acm
- 算法
- 动态规划
概述
背包问题就是动态规划的一个典型问题，，，个人觉得重在考查动态规划的思维，，有时需要将题目抽象出来，，，找出相对应的模型，，，然后优化解决，，，而不是一味的套模板。。。
这篇博客主要有 01背包问题 ， 完全背包问题 ， 多重背包问题 ， 混和背包问题 还有 二维费用背包问题，，，
概念知识点
01背包问题
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C_i ，得到的价值是 W_i 。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
定义状态：
F[i,v]表示把前i件物品放入容量为v的包中可以获得的最大价值。
状态转移方程：
F(i,v) = max(F(i-1,v),F(i-1,v-Ci)+Wi)
代码：
int c[N]; //第i个物品的代价
int w[N]; //第i个物品的价值
int f[N][N]; //f[i][j]表示将前i件物品放入容量为j的包是的最大的价值
F[0][0 - v] = 0;
for (int i = 1; i <= n; i++)
for (int j = c[i]; j <= v; j++)
f[i][j] = max(f[i - 1][j] , f[i - 1][j - c[i]] + w[i]);
时间复杂度为O(v * n)
空间复杂度可以继续优化到O(v)
将二维的f(i , v)改成一维的，，，逆序求即可
f[0 - v] = 0;
for (int i = 1; i <= n; i++)
for (int j = v; j >= c[i]; j--)
f[j] = max(f[j] , f[j - c[i]] + w[i]);
初始化细节
若题目要求 恰好好装满背包的最优解，，初始化：f[0] = 0; f[1 - v] = -INF;
若题目要求 不需要将背包装满 ，，，，，初始化：f[0 - v] = 0;
完全背包
习题
Problem A: 买东西
Time Limit: 1 Sec Memory Limit: 128 MB
Description
今天AveryBoy去一家诡异的店买东西。如果卡上的余额>=5，就一定可以买到东西，即使买完之后卡上余额为负；否则不能买到东西，即使卡上的余额足够。所以最后大家肯定都希望卡上的余额尽可能的少。
现在已知商店有n种商品并且每种商品只有一个，每种商品的价格和卡上余额，求最少能使卡上余额为多少？
Input
有多组输入数据，对于每组输入数据：
第一行为一个正整数n，n<=1000，表示商品的个数。
第二行为n个正整数，表示每种商品的价格，价格<=50。
第三行为一个正整数m，m<=1000，表示卡上的余额。
n=0表示输入结束。
Output
对于每组输入，输出卡上可能的最少余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32
我的代码：
//#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
const int N = 1e4;
int f[N];
int c[N];
int n , m;
int main()
{
while (cin >> n && n)
{
ms(f , 0);
ms(c , 0);
for (int i = 1; i <= n; i++)
{
cin >> c[i];
//w[i] = c[i];
}
int v;cin >> v;
if (v < 5)
{
cout << v << endl;
continue;
}
sort(c + 1 , c + 1 + n); //将最大的那个放最后
for (int i = 1; i < n; i++) //所以是n-1个
{
for (int j = v - 5; j >= c[i]; j--)
{
f[j] = max(f[j] , f[j - c[i]] + c[i]);
}
}
cout << v - f[v - 5] - c[n] << endl; //在添上最后哪一个最大的
}
return 0;
}
//5
//5 4 5 4 5
//15
//1
//50
//5
//10
//1 2 3 2 1 1 2 3 2 1
//50
//0
学长的代码：
// hdu 2546
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005],sz[1005];
int main()
{
int n,num;
while(~scanf("%d",&n)&&n)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&sz[i]);
}
sort(sz+1,sz+1+n);
scanf("%d",&num);
if(num<5)
{
printf("%d
",num);
continue;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<n;i++)
{
for(int j=num-5;j>=sz[i];j--)
{
dp[j] = max(dp[j],dp[j-sz[i]]+sz[i]);
}
}
printf("%d
",num-dp[num-5]-sz[n]);
}
return 0;
}
Problem B: 游戏
Time Limit: 1 Sec Memory Limit: 128 MB
Description
最近AveryBoy沉迷游戏，无法自拔。但是打怪升级的游戏玩久了很无趣，现在他还差n点经验就升到顶级了，但是他只剩m点忍耐度。每杀一个怪，他会得到对应的经验值，并减掉相应的忍耐度。当忍耐度<=0时，他就不会再玩游戏。并且他最多只杀s只怪。请问他能升到顶级吗？
Input
输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s <= 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b <= 20)；分别表示杀掉一只这种怪AveryBoy会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
Output
输出升到顶级还能保留的最大忍耐度，如果无法升到顶级输出-1。
Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
Sample Output
0
-1
1
我的代码：
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int c[N];
int w[N];
int n , m , k , s;
int main()
{
while (cin >> n >> m >> k >> s)
{
for (int i = 1; i <= k; i++)
cin >> w[i] >> c[i];
memset(f , 0 , sizeof(f));
bool flag = true;
for (int i = 1; i <= m; i++) //忍耐度
{
for (int j = 1; j <= k; j++) //怪的种数
{
for (int l = 1; l <= s; l++) //可杀的怪的数量
if (c[j] <= i)
f[i][l] = max(f[i][l] , f[i - c[j]][l - 1] + w[j]);
}
if (f[i][s] >= n)
{
cout << m - i << endl;
flag = false;
break;
}
}
if (flag) cout << "-1" << endl;
}
return 0;
}
学长的代码：
// hdu 2159
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int dp[105][105],a[105],b[105];
int main()
{
int n,m,k,s,tmp;
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{
for(int i=1;i<=k;i++) scanf("%d%d",&a[i],&b[i]);
memset(dp,0,sizeof(dp));
tmp=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=k;j++)
{
if(i<b[j]) continue;
for(int x=1;x<=s;x++)
{
for(int y=1;y<=x&&y*b[j]<=i;y++)
{
dp[i][x] = max(dp[i-y*b[j]][x-y]+y*a[j],dp[i][x]);
}
}
}
if(dp[i][s]>=n)
{
tmp=i;
break;
}
}
if(tmp==0) printf("-1
");
else printf("%d
",m-tmp);
}
return 0;
}
Problem C: 买东西2
Time Limit: 1 Sec Memory Limit: 128 MB
Description
你有n元钱，商店有m种商品，每种商品都有其对应的价格和重量。现在问你用这n元最多能买多重的商品。
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和商品的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每种商品的价格、重量以及个数。
Output
对于每组测试数据，请输出能够购买商品的最重的重量，你可以假设经费买不光所有的商品，并且经费你可以不用完。每个实例的输出占一行。
Sample Input
1
8 2
2 100 4
4 100 2
Sample Output
400
我的代码：
//#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
const int N = 1e4 + 3;
int f[N];
int w[N];
int c[N];
int m[N];
int pw[N];
int pc[N];
int main()
{
int t;cin >> t;
while (t--)
{
ms(f , 0);
ms(w , 0);
ms(c , 0);
ms(pw , 0);
ms(pc , 0);
ms(m , 0);
int n , mm;cin >> n >> mm;
for (int i = 1; i <= mm; i++)
{
cin >> pc[i];
cin >> pw[i];
cin >> m[i];
}
int num = 0;
for (int i = 1; i <= mm; i++)
{
int k = 1;
while (k < m[i])
{
w[num] = pw[i] * k;
c[num] = pc[i] * k;
num++;
m[i] -= k;
k <<= 1;
}
w[num] = pw[i] * m[i];
c[num] = pc[i] * m[i];
num++;
}
for (int i = 0; i < num; i++)
{
for (int j = n; j >= c[i]; j--)
{
f[j] = max(f[j] , f[j - c[i]] + w[i]);
}
}
cout << f[n] << endl;
}
return 0;
}
学长的代码:
// hdu 2191
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int dp[105],c[505],w[505];
int pc[105],pw[105],s[105];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&pc[i],&pw[i],&s[i]);
}
// 二进制拆分
int num = 0;
for(int i=1;i<=m;i++)
{
int k = 1;
while(k<s[i])
{
c[num] = pc[i]*k;
w[num] = pw[i]*k;
num++;
s[i]-=k;
k<<=1;
}
c[num] = pc[i]*s[i];
w[num] = pw[i]*s[i];
num++;
}
memset(dp,0,sizeof(dp));
for(int i=0;i<num;i++)
{
for(int j=n;j>=c[i];j--)
{
dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
}
}
printf("%d
",dp[n]);
}
return 0;
}
Problem D: 选课
Time Limit: 2 Sec Memory Limit: 128 MB
Description
AveryBoy这学期有n门课程，但由于他要去上班，导致他最多只有m天去学习这些课程。每门课程学习的天数不同会得到不同的分数，求他如何安排学习计划使得总分数最多。
Input
输入包含多组测试数据，每组测试数据第一行是两个正整数n，m。表示课程数和他学习的天数。
之后是n*m的矩阵，A[i][j]表示第i门课程学习j天会获得的分数。（1<=i<=n<=100，1<=j<=m<=100，1<=A[i][j]<=50）
输入以n=0，m=0结束。
Output
对于每组数据，输出AveryBoy能获得的最大分数。
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
我的代码:
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
int f[N];
int n , m;
int A[N][N];
int main()
{
while (cin >> n >> m && n && m)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> A[i][j];
memset(f , 0 , sizeof(f));
for (int k = 1; k <= n; k++) //将n个课程分组为1~k
{
for (int j = m; j >= 1; j--)
{
for (int i = 1; i <= m; i++) //对于每一组中的m个不同的方案
if (j - i >= 0) //当前天数够时
f[j] = max(f[j] , f[j - i] + A[k][i]);
}
}
cout << f[m] << endl;
}
return 0;
}
学长的代码:
// hdu 1712
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int sz[105][105],dp[105];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&sz[i][j]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=1;k<=m;k++)
{
if(j-k>=0) dp[j] = max(dp[j],dp[j-k]+sz[i][k]);
}
}
}
printf("%d
",dp[m]);
}
return 0;
}
鸽了，，，，