百练2755神奇的口袋(动态规划)

xiaoxiao2021-03-01  23

请点开我,我是题目哦!

递归解法:

#include<iostream> using namespace std; int a[25]={0},n; int Way(int w,int k); int main(){ int i,j; scanf("%d",&n); for(i = 1; i <= n; i++) scanf("%d",&a[i]); printf("%d\n",Way(40,n)); return 0; } int Way(int w,int k){//从前k种物品中选择一些,凑成体积 w的做法数目。 int i,j; if(w == 0) return 1; if(k <= 0) return 0; return Way(w,k-1) + Way(w-a[k],k-1); }

递推解法:

#include<iostream> using namespace std; int n,a[30]; int Way[40][30];//Ways[i][j]表示从前j种物品里凑出体积i的方法数 int main(){ scanf("%d",&n); // memset(Way,0,sizeof(Way)); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); Way[0][i] = 1;//边界条件 } Way[0][0] = 1;//边界条件 for(int w = 1; w <= 40; w++) for(int k = 1; k <= n; k++){ Way[w][k] = Way[w][k-1]; if(w - a[k] >= 0) Way[w][k] += Way[w-a[k]][k-1]; } printf("%d\n",Way[40][n]); return 0; }

转载请注明原文地址: https://www.6miu.com/read-3100064.html

最新回复(0)