pku 1837 Balance (01背包) - 小阮的菜田

随笔-141 评论-9 文章-3 trackbacks-0

01 背包问题.

f[i][j] 表示将前i个物品放入力矩为j的可行方案

f[i][j] = sum{ f[i-1][j-w[i][k] }

#include <iostream>

using namespace std;

const int mid = 6000;

int w[25],v[25];

int f[25][mid+mid];

int C,G;

int main(){

int i,j,k;

cin>>C>>G;

for(i=1; i<=C; ++i) cin>>v[i];

for(i=1; i<=G; ++i) cin>>w[i];

for(i=1; i<=C; ++i)

f[1][mid+v[i]*w[1]] = 1;

for(i=2; i<=G; ++i)

for(j=1; j<=C; ++j)

for(k=0; k<=2*mid; ++k)

if(f[i-1][k]>0)

f[i][k+w[i]*v[j]] += f[i-1][k];

cout<<f[G][mid]<<endl;

return 0;

}

posted on 2010-12-07 12:18 小阮阅读(106) 评论(0) 编辑收藏引用所属分类: POJ

只有注册用户登录后才能发表评论。


相关文章: pku 2774 Long Long Message (最长公共子串, 后缀数组) pku 3261 Milk Patterns ( 后缀数组, 二分答案) pku 1743 Musical Theme ( 后缀数组, 二分枚举答案) pku 1625 Censored! (AC自动机, DP, 高精度加法) pku 1204 Word Puzzles (trie) pku 1002 487-3279 (map) pku 2533 Longest Ordered Subsequence (DP) pku 3260 The Fewest Coins 多重背包+完全背包 pku 1276 Cash Machine 多重背包 pku 1948 Triangular Pastures (01背包)

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类