首页 > 代码库 > HDU 2844 Coins【多重背包】
HDU 2844 Coins【多重背包】
大意:
有n种物品
告诉你每种物品的价值和数量
问你能拼凑出1--m之内的多少个数
分析:
多重背包
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100005; 7 int dp[maxn]; 8 int num[maxn], va[maxn]; 9 int vo[maxn];10 int n, m;11 int tot;12 13 int solve() {14 int cnt = 0;15 memset(dp, 0, sizeof(dp));16 for(int i = 1; i < tot; i++) {17 for(int j = m; j >= vo[i]; j--) {18 dp[j] = max(dp[j], dp[j - vo[i]] + vo[i]);19 }20 }21 for(int i = 1; i <= m; i++) {22 if(dp[i] == i) cnt++;23 }24 return cnt;25 }26 27 int main() {28 while(scanf("%d %d",&n, &m) && ( n + m ) ) {29 for(int i = 1; i <= n; i++) {30 scanf("%d",&va[i]);31 }32 for(int i = 1; i <= n; i++) {33 scanf("%d",&num[i]);34 }35 tot = 1;36 for(int i = 1; i <= n; i++) {37 for(int k = 1; k <= num[i]; k *= 2) {38 vo[tot++] = k * va[i];39 num[i] -= k;40 }41 if(num[i]) vo[tot++] = num[i] * va[i];42 }43 printf("%d\n",solve());44 }45 return 0;46 }
HDU 2844 Coins【多重背包】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。