钢条切割
现有一段长度为n英寸的钢条和一个价格表pi,求切割方案使销售利益最大rn最大
类似于01背包
子问题为暴力求解中的组合价值。
此算法为自下而上 (botton-up method)
i用来遍历钢条长度，记录价值。
j用来遍历dp[i]数组内的数据，max取最大值，保存为dp[i]。
此原理可扩展到01背包
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
//算法导论-钢条切割-自下而上
int main(){
int p[11]={0,1,5,8,9,10,17,17,20,24,30};
int dp[101];
memset(dp,0,sizeof(dp));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]=max(dp[i],p[j]+dp[i-j]);
}
}
printf("%d",dp[n]);
}
运行结果
