Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

2. Gewichtsabwägung – Lanqiao Cloud Class (lanqiao.cn)

Ideen

Die Kernidee der dynamischen Programmierung besteht darin, das Problem in kleinere Teilprobleme zu zerlegen und die Lösungen der Teilprobleme zu speichern, um wiederholte Berechnungen zu vermeiden

Arraydp[i][j]Mittel vor GebrauchiDas Gewicht, das mit einem Gewicht gewogen werden kann, istjMenge

Der Update-Vorgang läuft wie folgt ab:

1. Initialisierung: dp[0][0] = 0;

2. Für jedes Gewicht wi:

 

AC-Code

#include<bits/stdc++.h>
typedef long long ll;
 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const ll M=2e5+10;
const int N=110;
int dp[N][M]={0};
using namespace std;
 
int main()
{
    IOS;
    int n,num=0;
    cin>>n;
    int w[N];
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        num+=w[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=num;j++)
        {
            dp[i][j] =  dp[i-1][j] + dp[i-1][abs(j-w[i])] + dp[i-1][j+w[i]];
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }
 
    for(int i=1;i<=num;i++)
    {
        if(dp[n][i]) ans++;
    }
    cout<<ans;
    return 0;
}