01Backpack Practice

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;
int dp[N];
int weight[N],value[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        //裸题
        memset(dp,0,sizeof(dp));
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        {
            cin>>value[i];
        }
        for(int i=1;i<=n;++i)
        {
            cin>>weight[i];
        }
        for(int i=1;i<=n;++i)
        {
            for(int j =m;j>=weight[i];--j)
            {
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;
int  dp[N],value[N];
int n,m;
int ans ;
int main()
{
    
    while(cin>>n&&n!=0)
    {
        
        memset(dp,0,sizeof(dp));
        for(int i =1;i<=n;++i)
        {
            cin>>value[i];
        }
        
        cin>>m;
        if(m<5)
            ans = m;
        else
        {
            //贪心，先买最贵的菜。
            m-=5;

            sort(value+1,value+1+n);
            //背包容量为m-5，物品数量为n-1的01背包问题
            
            for(int i=1;i<=n-1;++i)
            {
                for(int j =m;j>=value[i];j--)
                {
                    dp[j] =max(dp[j],dp[j-value[i]]+value[i]);
                }
            }
            ans = m+5 - dp[m]-value[n];
        }
        
        cout<<ans<<endl;
    }
    //system("pause");
    return 0;
}

状态方程为：dp[  j ] = max(dp[j], dp[j-w[i]]*(1-p[i]))

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;
double  dp[N];
double p[N];
int w[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        int n,sum=0;
        double m;//概率大于m会被抓
        cin>>m>>n;
        for(int i=1;i<=n;++i)
        {
            cin>>w[i]>>p[i];//输入每个银行钱数和抢劫他的概率
            sum+=w[i];//所有银行的钱数当做背包的容量，不被抓的概率当做价值
        }
        dp[0] = 1.0;
        for(int i=1;i<=n;++i)
        {
            for(int j =sum;j>=w[i];--j)
            {
                dp[j] = max(dp[j],dp[j-w[i]]*(1-p[i]));
                //不抢劫第i个银行，钱数减少w[i],并且逃走的概率增大。
            }
        }
        for(int i = sum;i>=0;i--)
        {
            if(dp[i]>=1-m)//逃走的概率大于1-m
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;
double dp[N];
int n,m;
int v[N];
double p[N];
int main()
{
    
    while(cin>>m>>n&&m+n)
    {
        for(int i =0;i<=m;++i)
            dp[i] = 1;
        int sum = 0;
        for(int i =1;i<=n;++i)
        {
            cin>>v[i]>>p[i];
           
        }
        
        for(int i =1;i<=n;++i)
        {
            for(int j = m; j >= v[i] ; --j )
            {
                dp[j] = min(dp[j],dp[j-v[i]]*(1-p[i]));//拿不到offer的最小值
            }
        }
        printf("%.1f%%\n",(1-dp[m])*100);
    }
    system("pause");
    return 0;
}