YCOJ完全背包问题
完全背包问题
Description
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
Input
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2…N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【YCOJ完全背包问题】Output
仅一行，一个数，表示最大总价值。
Sample Input 1
10 4
2 1
3 3
4 5
7 9
Sample Output 1
max=12
题意告诉我们，在不超过背包体积时，我们可以不断选择价值最大的物品，或者更优的把背包刚好装满。
文章图片
即dp[i][j]=max(dp[i][j-w[i]]+c[i],dp[i-1][j]);
所以dp[n][m]是最优解。
#include
using namespace std;
int n,m;
int a[1000],b[1000];
int dp[1000][1000];
int main(){
cin >> m >> n;
for(int i=1;
i<=n;
i++){
cin >> a[i] >> b[i];
}
for(int i=1;
i<=n;
i++){
for(int j=1;
j<=m;
j++){
for(int l=0;
l*a[i]<=j;
l++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-l*a[i]]+l*b[i]);
}
}
}
cout << "max="< 推荐阅读
- 别墅庭院设计，不同的别墅庭院设计也给人视觉上完全不一样的！
- 一份还算完全的挂耳咖啡指南
- 傻鸟的道理
- 《繁凡的深度学习笔记》|一文绝对让你完全弄懂信息熵、相对熵、交叉熵的意义《繁凡的深度学习笔记》第 3 章 分类问题与信息论基础（中）（DL笔记整理
- 特技摩托车
- 趋势，结构，位置，信号的完全分类
- 数据比较
- JQuery总结（选择器归纳、DOM遍历和事件处理、DOM完全操作和动画）
- 完全不一样的|完全不一样的 LaravelAdmin Windows Docker 搭建篇
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）