? ? 裸的01背包.dp[x]只要是bool型記錄當(dāng)前空間是否可用..

? ? 而為了找到用了哪些物品..dp[x]設(shè)置為int型..進(jìn)行記錄..

Program:

?

#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<cmath> #define oo 1000000007 #define ll long long #define pi acos(-1.0) #define MAXN 20005 using namespace std; int M,L,N,w[MAXN],dp[MAXN],ans[MAXN]; bool used[MAXN]; int main() {// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);int i,j,x,num,sum;while (~scanf("%d%d",&M,&L)){if (!M && !L) break;scanf("%d",&N);memset(dp,-1,sizeof(dp));sum=0;dp[0]=0;for (i=1;i<=N;i++) scanf("%d",&w[i]);for (i=1;i<=N;i++){x=w[i];sum+=x;for (j=M-x;j>=0;j--)if (dp[j]!=-1 && dp[j+x]==-1)dp[j+x]=i;}for (;M>=0;M--)if (sum-M<=L && dp[M]!=-1){x=M;num=0;while (x){ans[++num]=dp[x];x=x-w[dp[x]];}printf("%d",num);for (i=num;i>=1;i--) printf(" %d",ans[i]);break;}if (M<0) printf("Impossible to distribute");printf("\n");}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/snake-hand/p/3190225.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1293 - Duty Free Shop 01背包记录所选物品的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。