解题思路:
我们从最后一个物品开始考虑,有选和不选两种选项,当然需要满足条件:
total >= value[num]
即我们总的金钱需要能够买得起该物品,当我们选择买,状态就变成了:
OPT(total - value[num], num - 1) + weigth[num] * value[num]
我们的钱少了相应的值,增加了某个值,这个值就是题目所求的值,那么我们选不买的时候:
OPT(total, num - 1)
钱的数量没有改变,跳到下一个物品,而这两条方程就叫做状态转移方程。
那么是递归,我们就要考虑递归出口。
1. 当我们买不起的时候,我们没得选,只能移向下一个物品:
OPT(total, num - 1)
但当这个物品是最后一个物品的时候,我们买不了,所以返回的是 0;
2. 当我们能买当前物品,但该物品已经是最后一个了,我们就不需要考虑状态转移方程了,那么出口返回:
weigth[num] * value[num]( weigth[0] * value[0])
有了关系式子,又有了递归出口,那么整个递归就完成了。但有时候物品太多的时候递归就会 TLE,这时候就有了动态规划,核心也是状态转移方程。
参考代码:
#include<bits/stdc++.h> using namespace std; const int N = 25; int value[N], weigth[N]; int OPT(int total, int num) { if (total < value[num]) { if (num > 0) return OPT(total, num - 1); else return 0; } if (num == 0) return weigth[num] * value[num]; if (total >= value[num]) { int A = OPT(total - value[num], num - 1) + weigth[num] * value[num]; int B = OPT(total, num - 1); return A > B ? A : B; } } int main() { int total, num; cin >> total >> num; for (int i = 0; i < num; i++) cin >> value[i] >> weigth[i]; cout << OPT(total, num - 1); return 0; }
0.0分
6 人评分
背包问题 #include <stdio.h> int f[26][30001]={0}; int v[26]={0}; int w[26]={0}; void B(int M,int V) { int i,j; for(i=1;i<=M;i++) { for(j=1;j<=V;j++) { if(v[i]>j){ f[i][j]=f[i-1][j]; } else{ int a=f[i-1][j]; int b=f[i-1][j-v[i]]+(v[i]*w[i]); if(a>b) f[i][j]=a; else f[i][j]=b; } } } printf("%d\n",f[M][V]); } int main() { int N,m; scanf("%d%d",&N,&m); for(int i=1;i<=m;i++) scanf("%d%d",&v[i],&w[i]); B(m,N); return 0; }