DP-完全背包问题

题目：
有n件物品，每件物品的重量为w[i],价值为c[i]，现有一个容量为v的背包，问如何选取物品放入背包，使得背包内物品的总价值最大，其中每件物品都有无穷件。

思路：
dp[i][j]用来表示前I件物品，背包容量为j的物品最大价值
状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i])

Code：

//完全背包问题 
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 1010;
int v,n;
int w[maxn], c[maxn];
int dp[maxn][maxn];
void DP(){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i){
for(int j = w[i]; j <= v; ++j){
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]);
}
}
}
int main() {
//
fstream cin("a.txt");
cin >> n >> v;
for(int i = 0; i < n; ++i){
cin >> w[i];
}
for(int i = 0; i < n; ++i){
cin >> c[i];
}
DP();
cout << dp[n][v] <<endl;
return 0;
}

最后

以上就是野性酒窝为你收集整理的DP-完全背包问题的全部内容，希望文章能够帮你解决DP-完全背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。