完全背包问题

完全背包问题

【题目名称】

设有n种物品，每种物品有一个重量w和价值v。但每种物品的数量是无限的，同时有一个背包，最大载重量为m，从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于m，而价值的和最大。

【输入格式】 第一行：两个整数，m（背包容量，m<=200）和n(物品数量，n<=30)。

第二~n+1行：每行两个整数wi，ci，表示每个物品的重量和价值

【输出格式】 一个数据，表示最大总价值

【输入样例#1】

10 4

2 1

3 3

4 5

7 9

【输出样例#1】 12

#include<stdio.h> #include<string.h> int max(int x,inty){ if(x>y) return x; else return y; } int main(){ int m,n,i,j; int f[200],w[30],v[30]; memset(f,0,sizeof(f)); scanf("%d %d",&m,&n); for(i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]); for(i=0;i<n;i++) for(j=w[i];j<=m;j++){ f[j]=max(f[j-w[i]]+v[i],f[j]); } printf("%d\n",f[m]); return 0; }