01 backpack DP

A. Nine hours, nine people, nine doors （ 01 Knapsack for the number of solutions ）

link

#include<iostream>
using namespace std;
const int N=1e5+100,mod=998244353;
int a[N],f[N][10];
int count(int x)
{
    
    x%=9;
    if(x==0) return 9;
    return x;
}  
int main()
{
    
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++) cin>>a[i];
    
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=9;j++)
        {
    
            f[i][j]=(f[i][j]+f[i-1][j])%mod;
            f[i][count(a[i]+j)]=(f[i][count(a[i]+j)]+f[i-1][j])%mod;
        }
            
    for(int i=1;i<=9;i++)
        cout<<f[n][i]%mod<<" ";
    return 0;
}

B-01 Knapsack for the number of solutions

link

Writing a ： A two-dimensional

And the first scene A Do the same thing .
Be careful ：

1. $dp[i][j]$ Before presentation $i$ A watermelon , The weight of the watermelon that can be pieced together is $j$ The maximum number of schemes , Note that the two-dimensional array is opened a little larger according to the subject data range ！！（ At the beginning, the samples were all passed, but the answers were stuck here ）
2. $dp[0][0]=1$
3. In three cases, three recurrence formulas are obtained
   （1） The first i Choose no watermelon ,$dp[i][j]+=dp[i-1][j]$
   （2） Select No $i$ A watermelon , What matters is $j+w[i]$ and $j+w[i]/2$
   The first one is ：$dp[i][j+w[i]]+=dp[i-1][j]$
   The second kind ：$dp[i][j+w[i]/2]+=dp[i-1][j]$

#include<iostream>
using namespace std;
const int N=1100,mod=1e9+7;
long long dp[N][5000],w[N];

int main()
{
    
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) cin>>w[i];
    
    dp[0][0]=1;
    for(int i=1;i<=n;i++)   
        for(int j=0;j<=m;j++)
        {
    
            dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
            dp[i][j+w[i]]=(dp[i][j+w[i]]+dp[i-1][j])%mod;
            dp[i][j+w[i]/2]=(dp[i][j+w[i]/2]+dp[i-1][j])%mod;
        }
    
    for(int i=1;i<=m;i++) cout<<dp[n][i]%mod<<" ";
    return 0;
}

Write two : One dimensional scrolling array

$dp[i][j]=(dp[i-1][j]+dp[i-1][j-w[i]]+dp[i-1][j-w[i]/2])$%$mod$
Can be converted to a scrolling array ,$for$ Cycle the second layer $j$ Write in reverse order ,
$dp[j]=(dp[j]+dp[j-w[i]]+dp[j-w[i]/2])$%$mod$,
Add $if$ interpretation :
$if(j\ge w[i]),dp[j]=(dp[j]+dp[j-w[i]]+dp[j-w[i]/2])$%$mod$
$if(j\ge w[i]/2),dp[j]=(dp[j]+dp[j-w[i]]/2)$%$mod$

#include<iostream>
using namespace std;
const int N=1100,mod=1e9+7;
long long dp[N][5000],w[N];

int main()
{
    
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) cin>>w[i];
    
    dp[0][0]=1;
    for(int i=1;i<=n;i++)   
        for(int j=0;j<=m;j++)
        {
    
            dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
            dp[i][j+w[i]]=(dp[i][j+w[i]]+dp[i-1][j])%mod;
            dp[i][j+w[i]/2]=(dp[i][j+w[i]/2]+dp[i-1][j])%mod;
        }
    
    for(int i=1;i<=m;i++) cout<<dp[n][i]%mod<<" ";
    return 0;
}