给出背包容量 C,M 个物体, 接下来 M 行分别给出物品价值 V[i], 以及物品重量 W[i],
物品编号: 1 2 3
物品重量: 5 6 4
物品价值: 20 10 12
要使得放入背包的物品价值最大化, 我们知道用贪心肯定是不行的.
所以考虑动态规划, 首先定义状态 dp[i][j]为放入前 i(i 从小到大)个物品的最大价值, 那么 i 等于 1 的时候, 放入的是物品 1, 这时候肯定是最优的.
接下来考虑一下 j, j 是当前容量; 如果 j <5, 就不能放, dp[1][j]=0; 那如果 j> 5m 就可以放了, dp[1][j] = 20;
接着 i = 2 放第二个物品的时候, 求得就是 dp[2][j] 了, 当 j <5 的时候 , 同样的 dp[2][j] = 0; 那当 j<6 的时候, 是不是还是放不下第二个, 只能放第一个.
那么想一下, 是不是当 j>6 的时候, 就可以放第二个了呢? 答案是可以的, 但结果明显不是最优的, 想一下, dp[2][j]=20, 这个 20 是怎么来的呢, 当然是从前一个状态来的(注意这里分为两种情况)
一种是选择第二个物品放入, 另一种还是选择前面的物品;
让我们假设一下, j = 10 吧, 这时候 dp[2][10] = max(dp[1][ 10 - w[2] ]+V[2] , dp[1][10] ); 即 dp[2][10] = max(dp[1][4])+10,dp[1][10]);
结果是不是很明显了, dp[1][4])+10 是选择了第二个, 于是容量相应就减少成 4, 之前已经得出 dp[1][4]=0, 就是说选了物品 2, 物品 1 就选不了了; dp[1][10]是不选择第二个, 只选择第一个 dp[1][10]是等于 20 的, 于是得出 dp[2][10]=20;
推到这里, 我们类比往下推, 就可以得出动态状态转移方程 ,dp[i][j] = max( dp[i-1][j - W[i] ]+ V[i] , dp[i-1][j] )
但是好像还有一些问题没考虑完.........
看回例子:
物品编号: 1 2 3
物品重量: 5 6 4
物品价值: 20 10 12
我们知道 dp[1] https://www.luogu.org/problemnew/solution/j<5 =20,dp[2] https://www.luogu.org/problemnew/solution/j=5 的时候是多少呢? 我们看到动态转移方程并没有考虑 j<w[i]的情况, 但是我们可以加进去, 由于 dp[2][5]我们看出来是等于 5 的, 为什么? 因为不能选第二个, 只能选第一个, 所以.....dp[2][5]是不是刚好等于 dp[1][5]了呢! 所以当 j<w[i]的时候, dp[i][j] = dp[i-1][j]就好了.
接下来上一道例题:
题目描述
辰辰是个天资聪颖的孩子, 他的梦想是成为世界上最伟大的医师. 为此, 他想拜附近最有威望的医师为师. 医师为了判断他的资质, 给他出了一个难题. 医师把他带到一个到处都是草药的山洞里对他说:"孩子, 这个山洞里有一些不同的草药, 采每一株都需要一些时间, 每一株也有它自身的价值. 我会给你一段时间, 在这段时间里, 你可以采到一些草药. 如果你是一个聪明的孩子, 你应该可以让采到的草药的总价值最大."
如果你是辰辰, 你能完成这个任务吗?
输入输出格式
输入格式:
第一行有 222 个整数 T(1≤T≤1000)T(1 \le T \le 1000)T(1≤T≤1000)和 M(1≤M≤100)M(1 \le M \le 100)M(1≤M≤100), 用一个空格隔开, TTT 代表总共能够用来采药的时间, MMM 代表山洞里的草药的数目.
接下来的 MMM 行每行包括两个在 111 到 100100100 之间 (包括 111 和 100100100) 的整数, 分别表示采摘某株草药的时间和这株草药的价值.
- 70 3
- 71 100
- 69 1
- 1 2
输出格式:
111 个整数, 表示在规定的时间内可以采到的草药的最大总价值.
- 3
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int maxn=100+10;
- int w[maxn],val[maxn];
- int dp[maxn][1005];
- int main(){
- int t,m;
- cin>>t>>m;
- for( int i=1; i<=m; i++ ){
- cin>>w[i]>>val[i];
- }
- for( int i=1; i<=m; i++ ){
- for( int j=t; j>=0; j-- ){
- if(j>=w[i]){
- dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);
- }
- else{
- dp[i][j]=dp[i-1][j];
- }
- }
- }
- cout<<dp[m][t];
- return 0;
- }
01 背包问题(动态规划)
来源: http://www.bubuko.com/infodetail-2947305.html