朴素递归算法(时间超限)
参考代码:
#include <stdio.h> int t,m; typedef struct Item { int time; int val; }item; item a[101]; int max(int a,int b) { return a>b?a:b; } int f(int i,int Capacity) { if(i==m) return (Capacity<a[i].time)?0:a[i].val; if(Capacity<a[i].time) return f(i+1,Capacity); return max(f(i+1,Capacity),f(i+1,Capacity-a[i].time)+a[i].val); } int main() { int i; scanf("%d %d",&t,&m); getchar(); for(i=1;i<=m;i++) { scanf("%d %d",&a[i].time,&a[i].val); getchar(); } int tval=f(1,t); printf("%d",tval); return 0; }
2.无重复计算的背包问题(正确),采用二维数组存储对应第几株草多少剩余时间的条件下的最优解(最大价值)
#include <stdio.h> int t,m; int ftmp[101][1001]; typedef struct Item { int time; int val; }item; item a[101]; int max(int a,int b) { return a>b?a:b; } int f(int i,int Capacity) { if(ftmp[i][Capacity]>=0) return ftmp[i][Capacity]; if(i==m) { ftmp[i][Capacity]=(Capacity<a[i].time)?0:a[i].val; return ftmp[i][Capacity]; } if(Capacity<a[i].time) ftmp[i][Capacity]=f(i+1,Capacity); else ftmp[i][Capacity]=max(f(i+1,Capacity),f(i+1,Capacity-a[i].time)+a[i].val); return ftmp[i][Capacity]; } int main() { int i,j; scanf("%d %d",&t,&m); getchar(); for(i=1;i<=m;i++) for(j=1;j<=t;j++) ftmp[i][j]=-1; for(i=1;i<=m;i++) { scanf("%d %d",&a[i].time,&a[i].val); getchar(); } int tval=f(1,t); printf("%d",tval); return 0; }
0.0分
0 人评分
A+B for Input-Output Practice (V) (C++代码)浏览:451 |
A+B for Input-Output Practice (VI) (C++代码)浏览:417 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:559 |
剪刀石头布 (C语言代码)浏览:752 |
IP判断 (C语言描述,蓝桥杯)浏览:1095 |
1009题解浏览:750 |
数对 (C语言代码)浏览:702 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:587 |
Tom数 (C语言代码)浏览:555 |
分糖果 (C语言代码)浏览:920 |