题目
将以下代码复制到代码编辑器中,在编写区域编写代码
#include<iostream> #include<vector> using namespace std; //01背包问题 void test_bag_problem(){ vector<int> weight={1,3,4}; vector<int> value={15,20,30}; int bagweight=4;//背包容量 //****************编写代码*************// //*************************************// //输出dp cout<<dp[bagweight]<<endl; } int main(){ test_bag_problem(); system("pause"); return 0; }
解题
方法一:二维dp的方法
void test_2_wei_bag_problem(){ vector<int> weight={1,3,4}; vector<int> value={15,20,30}; int bagweight=4;//背包容量 vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0)); for(int j=weight[0];j<=bagweight;j++){ dp[0][j]=value[0]; } for(int i=1;i<weight.size();i++){ for(int j=0;j<=bagweight;j++){ if(j<weight[i]) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); } } for(vector<int> vec:dp){ for(int val:vec){ cout<<val<<" "; } cout<<endl; } } int main(){ test_2_wei_bag_problem(); system("pause"); return 0; }
方法二:一维dp(滚动数组)
c++写法
void test_1_wei_bag_problem() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector<int> dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight] << endl; } int main() { test_1_wei_bag_problem(); }
java写法
public class Main { public static void main(String[] args) { int[] weight={1,3,4}; int[] value={15,20,30}; int bagWeight=4; int[] dp=new int[bagWeight+1]; for(int i=0;i<weight.length;i++){ for(int j=bagWeight;j>=weight[i];j--){ dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]); } } System.out.println(dp[bagWeight]); } }
补充:
总结背包问题:
01背包:反向遍历背包容量
完全背包:正向遍历背包容量
组合问题:先遍历物品再遍历容量(遍历过的物品不会再遍历,因此不涉及排序的问题)
排列问题:先遍历容量再遍历物品