洛谷P2347 砝碼稱重 某一年noip提高組原題

可以轉化為01背包求方案數的問題，dp數組f[][]表示第幾個砝碼能稱出的重量,可壓縮至一維 轉移方程為f(i,j)+=f(i-1,j-w[i])?當前我們可以稱出的重量必定是由之前的砝碼重量轉移過來的

#include<bits/stdc++.h>
using namespace std;
const int N=550;
const int maxn=1e6+7;
int f[maxn];
int a[maxn];
int v[maxn];//相當于01背包的物品重量
int num[10]={0,1,2,3,5,10,20};//砝碼重量
int cnt; 
int maxsum;
int ans;
int main()
{for(int i=1;i<=6;i++){scanf("%d",&a[i]);for(int j=1;j<=a[i];j++){v[++cnt]=num[i];//統計
        }}for(int i=1;i<=cnt;i++){maxsum+=v[i];//背包的最大容量
    }f[0]=1;//0也是一種方案，初始狀態for(int i=1;i<=cnt;i++)//01背包
    {for(int j=maxsum;j>=v[i];j--){f[j]+=f[j-v[i]];}}for(int i=1;i<=maxsum;i++)//統計方案個數
    {if(f[i]){ans++;}}printf("Total=%d",ans);return 0;
}

?