动态规划水题集

对于巨佬而言真的就是水题了，作为一个蒟蒻我还是从水题开始慢慢写吧

hdu 2602 Bone Collector

01背包模板题，用这道题写写01背包的几种写法吧

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
int val[maxn];
int pla[maxn];
int dp[maxn][maxn];
int N,V;
void solve()
{
    for (int i=1;i<=N;i++)
    {
        for (int j=0;j<=V;j++)
        {
            if (j>=pla[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-pla[i]]+val[i]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
}
int choose[maxn];//这个是用来记录选择了哪个物品的
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        memset(dp,0,sizeof(dp));
        cin>>N>>V;
        for (int i=1;i<=N;i++) cin>>val[i];
        for (int i=1;i<=N;i++) cin>>pla[i];
        solve();
        cout<<dp[N][V]<<endl;//忘了写endl搞了个PE...
        /*int n=N,v=V;这一段就是找寻找物品的，我就注释掉了
        while (dp[n][v])一直循环找选择的物品
        {
            if (dp[n][v]==dp[n-1][v])
                choose[n]=0;
            else
            {
                choose[n]=1;
                v=v-pla[n];开始忘了减...
            }
            n--;
        }
        for (int i=1;i<=N;i++)
            cout<<choose[i]<<" ";*/
    }
    return 0;
}

//滚动数组的代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
int val[maxn];
int pla[maxn];
int dp[maxn];
int N,V;
void solve()
{
    for (int i=1;i<=N;i++)
        for (int j=V;j>=pla[i];j--)//最开始还多写了个if来判断j是不是大于pla[i]，看了看AC代码发现写一起就行了...还是太弱
                dp[j]=max(dp[j],dp[j-pla[i]]+val[i]);//标准背包状态转移方程
}
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        memset(dp,0,sizeof(dp));//别忘了清0
        cin>>N>>V;
        for (int i=1;i<=N;i++) cin>>val[i];
        for (int i=1;i<=N;i++) cin>>pla[i];
        solve();
        cout<<dp[V]<<endl;
    }
    return 0;
}

动态规划水题集

原文：https://www.cnblogs.com/Salty-Fish/p/12497499.html