#背包
0/1背包
容量为V的背包
需要在k个物品中选取并装入
只有装/不装两种状态
v[i]
w[i]
dp[i][j]
求解dp[i][j]
必然已求得dp[1i-1][1j-1]
不装入:dp[i][j] = dp[i-1][j]
选择装入dp[i][j] = dp[i-1][j-v[i]]+w[i];
初始化:dp[0][0~v] = 0;
答案:dp[k][v]
滚动数组优化
压成一维
#无限背包
容量为V的背包
需要在k个物品中选取并装入
每种物品可以选取任意个数
每个物品占用空间v[i],价值w[i];
不装入
dp[i][j] = dp[i-1][j]
装入
dp[i][j] = dp[i][j-v[i]]+w[i];
j的循环从小到大
一个int4个字节
32位一个int