UVA 624 ---CD 01背包路径输出
DescriptionCD
Assumptions:
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Set of tracks (and durations) which are the correct solutions and string `` sum:" and sum of duration times
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2
1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45
01背包输出路径;
#include<stdio.h> #include<string.h> #define N 1100 #define max(a,b) (a>b?a:b) int v[N], dp[N][N], W, n; void Path(int n, int W) { if(n==0) return ; if(dp[n-1][W]==dp[n][W]) Path(n-1, W); else { Path(n-1, W-v[n]); printf("%d ", v[n]); } } int main() { while(scanf("%d%d", &W, &n)!=EOF) { int i, j; memset(v, 0, sizeof(v)); memset(dp, 0, sizeof(dp)); for(i=1; i<=n; i++) scanf("%d", &v[i]); for(i=1; i<=n; i++) for(j=0; j<=W; j++) { if(v[i]>j) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]); } Path(n, W); printf("sum:%d\n", dp[n][W]); } return 0; }View Code
一维数组:
#include<iostream> #include<stdio.h> #include<algorithm> #include<math.h> #include<string.h> #include<string> #include<stack> #include<vector> #include<map> using namespace std; #define N 2510 #define INF 0x3f3f3f3f #define met(a, b) memset(a, b, sizeof(a)) typedef long long LL; int n, m, a[N], dp[N], path[N][N]; int main() { while(scanf("%d %d", &m, &n)!=EOF) { met(dp, 0); met(path, 0); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=0; i<n; i++) { for(int j=m; j>=a[i]; j--) { ///dp[j] = max(dp[j], dp[j-a[i]]+a[i]); if(dp[j] < dp[j-a[i]]+a[i]) { path[i][j] = 1; dp[j] = dp[j-a[i]]+a[i]; } } } int j = m, k = 1, ans[N] = {0}; for(int i=n-1; i>=0; i--) { if(path[i][j]) { ans[k++] = a[i]; j -= a[i]; } } for(int i=k-1; i>=1; i--) printf("%d ", ans[i]); printf("sum:%d\n", dp[m]); } return 0; }View Code 优质内容筛选与推荐>>