生活随笔
收集整理的這篇文章主要介紹了
【UVA624 01背包中的路径问题】
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
UVA624
給你一個序列，讓你從其中選出一些數，然后得到最接近題目所給的一個數，并需要輸出所選的數
考察o1背包容量是從大到小容量減少的方式來進行裝入的，
路徑記錄，感覺好題啊
初始化為求正好放滿的模型
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=10001;
int w[30],dp[maxn];
bool mp[maxn][30];
int sum,n;
int main()
{while(scanf("%d%d",&sum,&n)!=EOF){memset(mp,0,sizeof(mp));memset(dp,0,sizeof(dp));for(int i=0;i<n;i++) scanf("%d",&w[i]);for(int i=0;i<n;i++)for(int j=sum;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+w[i]);if(dp[j]==(dp[j-w[i]]+w[i]))mp[j][i]=true;}for(int i=n-1,j=sum;i>=0;i--){if(mp[j][i]){printf("%d ",w[i]);j-=w[i];}}printf("sum:%d\n",dp[sum]);}return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<iostream>
using namespace std;
int dp[111000],vis[50][111000];
int f[50],k=0,w[50];
void prime(int n,int m)
{if(n==0||m<0)return;if(vis[n][m]==0)prime(n-1,m);else{prime(n-1,m-w[n]);f[k++]=w[n];;}
}
int main()
{int m,n,i,j;while(scanf("%d",&m)!=EOF){memset(w,0,sizeof(w));scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&w[i]);}memset(dp,0,sizeof(dp));memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){for(j=m;j>=w[i];j--){if(dp[j]<dp[j-w[i]]+w[i]){dp[j]=dp[j-w[i]]+w[i];vis[i][j]=1;}}}k=0;memset(f,0,sizeof(f));prime(n,m);for(i=0;i<k;i++)printf("%d ",f[i]);printf("sum:%d\n",dp[m]);}return 0;
}
?
總結
以上是生活随笔為你收集整理的【UVA624 01背包中的路径问题】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
