背包问题及其变形

hdu 2546

题目意思：食堂买菜，只要余额大于5圆就可以买任意的菜，问最少余额为多少。

思路：把5圆留着购买最贵的菜，其余的直接0-1背包即可，有点贪心的思想。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include<algorithm>
 5 #define maxn 1010
 6 #define INF 0x3ffffff
 7 using namespace std;
 8 int dp[maxn];
 9 int n,m;
10 int w[maxn];
11 int main ()
12 {
13     while(scanf("%d",&n),n)
14     {
15         for(int i=0;i<n;++i)scanf("%d",&w[i]);
16         sort(w,w+n);
17         scanf("%d",&m);
18         if(m<5){printf("%d
",m);continue;}
19         m-=5;
20         for(int i=0;i<=m;++i)dp[i]=m;
21         for(int i=n-2;i>=0;--i)
22         {
23             for(int j =m;j>=w[i];--j)
24             {
25                 dp[j]=min(dp[j],dp[j-w[i]]-w[i]);
26             }
27         }
28         int ans = INF;
29         for(int i=0;i<=m;++i)ans = min(ans,dp[i]);
30         printf("%d
",ans+5-w[n-1]);
31     }
32 }

View Code

uva 624

0-1背包记录路径

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxn 1010
 5 using namespace std;
 6 int dp[maxn];
 7 int n,m;
 8 int w[maxn];
 9 int path[maxn][maxn];
10 int main ()
11 {
12     while(scanf("%d%d",&m,&n)!=EOF)
13     {
14         for(int i=1; i<=n; ++i)scanf("%d",&w[i]);
15         memset(dp,0,sizeof(dp));
16         memset(path,0,sizeof(path));
17         for(int i=n; i>=1;--i)
18         {
19             for(int j =m; j>=w[i]; --j)
20             {
21                 if(dp[j-w[i]]+w[i]>dp[j])
22                 {
23                     dp[j]=dp[j-w[i]]+w[i];
24                     path[i][j]=1;
25                 }
26             }
27         }
28         for(int i=1,j=m;i<=n;++i)
29         {
30             if(path[i][j]){printf("%d ",w[i]);j-=w[i];}
31         }
32         printf("sum:%d
",dp[m]);
33     }
34 }

View Code

hdu 2126

0-1 背包记录方案数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define maxn 5010
 5 #include<algorithm>
 6 using namespace std;
 7 int dp[maxn];
 8 int n,m;
 9 int w[maxn];
10 int path[maxn];
11 int used[maxn];
12 int main ()
13 {
14     int t;
15     scanf("%d",&t);
16     while(t--)
17     {
18         scanf("%d%d",&n,&m);
19         for(int i=1;i<=n;++i)scanf("%d",&w[i]);
20         memset(dp,0,sizeof(dp));
21         memset(path,0,sizeof(path));
22         for(int i=0;i<=m;++i)path[i]=1;
23         for(int i=1;i<=n;++i)
24         {
25             for(int j=m;j>=w[i];--j)
26             {
27                 if(dp[j-w[i]]+1>dp[j])
28                 {
29                     dp[j]=dp[j-w[i]]+1;
30                     path[j]=path[j-w[i]];
31                 }
32                 else if(dp[j-w[i]]+1==dp[j])
33                 {
34                     path[j]+=path[j-w[i]];
35                 }
36             }
37         }
38         if(dp[m]==0){printf("Sorry, you can't buy anything.
");continue;}
39         printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.
",path[m],dp[m]);
40     }
41 }

View Code