首页 > 代码库 > poj1742 Coins
poj1742 Coins
思路:
多重背包变形。
楼天城男人八题的第六题。
http://www.cnblogs.com/dramstadt/p/3439725.html
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 bool ok[100005]; 6 int used[100005]; 7 int v[105]; 8 int c[105]; 9 int n,m; 10 int main() 11 { 12 while(cin >> n >> m, n + m) 13 { 14 for(int i = 0; i < n; i++) 15 { 16 scanf("%d", &v[i]); 17 } 18 for(int i = 0; i < n; i++) 19 { 20 scanf("%d", &c[i]); 21 } 22 int cnt = 0; 23 memset(ok, 0, sizeof(ok)); 24 ok[0] = true; 25 for(int i = 0; i < n; i++) 26 { 27 memset(used, 0, sizeof(used)); 28 for(int j = v[i]; j <= m; j++) 29 { 30 if(!ok[j] && ok[j-v[i]] && used[j-v[i]] < c[i]) 31 { 32 ok[j] = true; 33 used[j] = used[j-v[i]] + 1; 34 cnt++; 35 } 36 } 37 } 38 cout << cnt << endl; 39 } 40 return 0; 41 }
poj1742 Coins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。