做网站的颜色搭配,网站兼职做计划赚小钱,设计开发控制程序,给公司做网站 图片倾权题目描述#xff1a; 有若干张邮票#xff0c;要求从中选取最少的邮票张数凑成一个给定的总值 如#xff0c;有1分#xff0c;3分#xff0c;3分#xff0c;3分#xff0c;4分五张邮票#xff0c;要求凑成10分#xff0c;则使用3张邮票#xff1a;3分、3分、4分即…题目描述 有若干张邮票要求从中选取最少的邮票张数凑成一个给定的总值 如有1分3分3分3分4分五张邮票要求凑成10分则使用3张邮票3分、3分、4分即可 思路 1. 朴素背包问题 2. 假设 dp[i][j] 表示前 i 件物品拼成 j 分的最少邮票数 dp[i][j] min(dp[i-1][j], dp[i-1][j-value[i]]1) 3. 转化成一维背包 dp[v] min(dp[v], dp[v-value[i]]1) 代码 未通过九度测试 #include iostream
#include stdio.h
#include memory.h
using namespace std;const int INF 0X3F3F3F3F;
int M, N;
int stamps[200];
int dp[200];int main() {freopen(testcase.txt, r, stdin);while(scanf(%d, M) ! EOF) {scanf(%d, N);for(int i 0; i N; i ) {scanf(%d, stampsi);}memset(dp, 0x3F, sizeof(dp));dp[0] 0;for(int i 0; i N; i ) {for(int v M; v stamps[i]; v --) {dp[v] min(dp[v], dp[v-stamps[i]]1);}}if(dp[M] INF)cout 0 endl;elsecout dp[M] endl;}return 0;
}
