poj 3624 && hdu 2955(背包入门)

背包中最基础的01背包,大意是有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大

主要是要有动态规划的思想,列出每个容量下的最大值,每次只考虑取或不取两种情况《一个状态一个状态的转移

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int dp[12900];
 5 int w[3410],d[3410];
 6 int main()
 7 {
 8     int n,m,i,j;
 9     while (cin>>n>>m)
10     {
11         for (i=1;i<=n;i++)
12             cin>>w[i]>>d[i];
13         memset(dp,0,sizeof(dp));
14         for (i=1;i<=n;i++)
15         {
16             for (j=m;j>=w[i];j--)
17                 dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
18         }
19         cout<<dp[m]<<endl;
20     }
21     return 0;
22 }

http://acm.hdu.edu.cn/showproblem.php?pid=2955

有小数不好处理,所以逆向考虑,把抢银行的价值作为容量来转移

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int a[101];
 5 double b[101],dp[100001];
 6 double max(double x,double y)
 7 {
 8     if (x>y) return x;
 9     else return y;
10 }
11 int main()
12 {
13     int t,m,i,j;
14     double n;
15     while (~scanf("%d",&t))
16     {
17         while (t--)
18         {
19             scanf("%lf %d",&n,&m);
20             int sum=0;
21             for (i=1;i<=m;i++)
22             {
23                scanf("%d %lf",&a[i],&b[i]);
24                sum+=a[i];
25             }
26             memset(dp,0 ,sizeof(dp));
27             dp[0]=1;
28             for (i=1;i<=m;i++)
29             {
30                 for (j=sum;j>=a[i];j--)
31                     dp[j]=max(dp[j],(1-b[i])*dp[j-a[i]]);
32             }
33             int ans=0;
34             for (i=1;i<=sum;i++)
35             {
36                 //printf("%lf
",dp[i]);
37                 if ((1-dp[i])<=n&&ans<i) ans=i;
38             }
39             printf("%d
",ans);
40         }
41     }
42     return 0;
43 }