题目简介:
有大小为10 20 50 100 的四种物品,装入容量为 n 的背包,问刚好装满背包的方法数
样例1:
输入 0
输出 0
样例2:
输入 100
输出 11
样例3:
输入 15
输出 0
注意事项:
- 由于大小都是10的倍数,可进行判断:
若容量n是10的倍数,则将n除以2,物品大小以1 2 5 10计算;
若容量n不是10的倍数,则输出0,程序结束。思路:
循环4个物品大小与1~n的容量,两者相减得到一个容量,此容量指放入当前循环物品前的容量,放入当前物品后此容量的个数等于放入前个数(如原容量方法数为2,有2种,这两种方法中各加入大小为5的物品,方法数依然为2,于是将2加入容量为7的方法数)
代码:
#includeusing namespace std; int dp[1001]; int main(){ int n; cin >> n; int a[4] = {1,2,5,10}; dp[0] = 1; if (n % 10 == 0) n /= 10; else{ cout << 0 << endl; return 0; } for(int i = 0; i < 4; i++) for(int j = a[i]; j <= n; j++) dp[j] += dp[j - a[i]]; cout << dp[n] << endl; return 0; }
End
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)